hdu 4946 Area of Mushroom 共线凸包 附赠数据,点击就送

这题要用水平排序来做,用极坐标排序得要在最几个点特判一下. 做题时太年轻,用了极坐标排序,wa到死..

不能用极坐标排序的原因:http://blog.csdn.net/u013532224/article/details/38587137

并且亲测共线要去重.否则也得wa. 当然如果是普通的非共线图包题就不用去重了.

还有疑惑的地方就是数组开507会爆栈,得要到1007,不知道为什么,囧.

Area of Mushroom

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1466    Accepted Submission(s): 355

Problem Description

Teacher Mai has a kingdom with the infinite area.

He has n students guarding the kingdom.

The i-th student stands at the position (x _i,y _i), and his walking speed is v _i.

If a point can be reached by a student, and the time this student walking to this point is  strictly less than other students, this point is in the charge of this student.

For every student, Teacher Mai wants to know if the area in the charge of him is infinite.

 

Input

There are multiple test cases, terminated by a line "0".

For each test case, the first line contains one integer n(1<=n<=500).

In following n lines, each line contains three integers x _i,y _i,v _i(0<=|x _i|,|y _i|,v _i<=10^4).

 

Output

For each case, output "Case #k: s", where k is the case number counting from 1, and s is a string consisting of n character. If the area in the charge of the i-th student isn't infinite, the i-th character is "0", else it's "1".

 

Sample Input

3 0 0 3 1 1 2 2 2 1 0

 

Sample Output

Case #1: 100

题意是有n个学霸,,  每个人用x,y, v来表示. x,y,是坐标,v是他的速度.

如果某学霸能到某个地方比任何人都快(同时到达不算), 那么 那块位子就被他承包了.

如果某学霸可以承包无限多的位子对应地输出1, 不能就输出0;

思路, 速度快的,永远能追上速度小的, 所以承包无限大的鱼塘的学霸,肯定是速度最快的学霸.

那么就把速度最快的学霸都挑出来. 然后跑凸包,凸包上的点,就是可以无限承包地方的学霸.

证明是这样的,如下图如果两个学霸 a,b 速度都一样快,那么以虚线,也就是中垂线,为界限,左边的A块是a 的. B是b的

有了上面的结论后,再看下图, 跑完凸包后  a-e 都是凸包上的端点, g是凸包线上的某点, f是凸包内的点

如果先不考虑其他点, a g, b的界限是下图这样的, 同样以两条虚线为界限.  因为其他点,  都在这三点下面, 所以显然a,g,b 能在其各自上端,得到无限大的扩张区域.

再单独考虑,a,b,f 三个点, 图中虚线有重合的点,  再往上, 区域就要被a,b 中垂线均分了.  f可以的到的只有涂成红色的区域.   其他边同理也是这样.  所以最后 在凸包里的点,都会像f一样只能承包一部分的鱼塘

当然,这题有很多地方要注意的,如最大值都是0, 那么所有点都不能承包无限大的区域.

如果有有两个点速度都是最大的,而且是重点, 那么重点是不能承包无限大区域的.但是重点会对其他点产生影响,所以要去重后,同样要去跑凸包.

#include <cstdio>  
#include <cstring>  
#include <cmath>  
#include <queue>  
#include <iostream>  
#include <algorithm>  
#include <map>
using namespace std;  
const int maxn=1007;  
const double pi=atan(1.0)*4;  
struct node{  
    int x,y;
	int code;
}e[maxn],res[maxn];  
int m;
int cmp(node a,node b)  
{  
    if(a.x==b.x)return a.y<b.y;  
    return a.x<b.x;  
}  
int cross(node a,node b,node c)//向量积  
{  
    return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);  
}  
void convex(int n)//求凸包上的点  存在res中,下标(0,m]
{  
    sort(e,e+n,cmp);  
    int i,j,k;
	m=0;
    //求得下凸包，逆时针  
    //已知凸包点m个，如果新加入点为i，则向量(m-2,i)必定要在(m-2,m-1)的逆时针方向才符合凸包的性质  
    //若不成立，则m-1点不在凸包上。  
    for(i=0;i<n;i++)  
    {  
        while(m>1&&cross(res[m-1],e[i],res[m-2])<0)m--;  
        res[m++]=e[i];  
    }  
    k=m;  
    //求得上凸包  
    for(i=n-2;i>=0;i--)  
    {  
        while(m>k&&cross(res[m-1],e[i],res[m-2])<0)m--;  
        res[m++]=e[i];  
    }  
    if(n>1)m--;//起始点重复。  
}  
 int main()
{
    int n,max,cas=1,sum;
    int num2[1007],x[1007],y[1007],a[1007];
    int  b,c,i,flag;
    map<pair<int,int>,int > my;
    map<pair<int,int>,int > my2;
    map<pair<int,int>,int > my3;
 
    while(scanf("%d",&n),n)
    {
        my.clear();//记录其最大值
        my2.clear();//记录是不是重点,输入的时候用,
        my3.clear();//记录是不是重点,筛选点到凸包的时候用.


        max=-1;
        for(i=0;i<n;i++)
        {
            scanf("%d%d%d",&x[i],&y[i],&a[i]);
            if(!my.count(make_pair(x[i],y[i]))&&a[i]>=max)
            {
                my[make_pair(x[i],y[i])]=a[i];
                my2[make_pair(x[i],y[i])]=1;
            }
            else if (a[i]>=max)
            {
                if(my[make_pair(x[i],y[i])]<a[i])
                {
                    my[make_pair(x[i],y[i])]=a[i];
                    my2[make_pair(x[i],y[i])]=1;
                }
                else if (my[make_pair(x[i],y[i])]==a[i])
                    my2[make_pair(x[i],y[i])]=0;
            }
            if(a[i]>max)
                max=a[i];
        }


        printf("Case #%d: ",cas++);
        if(max==0)//都是0
        {
            for(i=0;i<n;i++)
            {
                printf("0");
            }
            puts("");
            continue;
        }

        sum=0;
        for(i=0;i<n;i++)//把v最大的点用来跑凸包,并且要去重
        {
            if(a[i]==max&&my3.count(make_pair(x[i],y[i]))==0)
            {
                my3[make_pair(x[i],y[i])]=1;
                e[sum].x=x[i];
                e[sum].y=y[i];
                e[sum++].code=i;
            }
        }
        if(sum>=4)//四个以上的点跑凸包, 找到凸包上的点.
        {
            convex(sum);
            memset(num2,0,sizeof(num2));
            for(i=0;i<m;i++)
            {
                num2[res[i].code]=1;//凸包上的点的标号是要输出1的,由num2 记录
            }
            for(i=0;i<n;i++)
            {
                if(my2[make_pair(x[i],y[i])]==1)//my2看是不是重点
                    printf("%d",num2[i]);
                else
                    printf("0");
            }
            puts("");
            continue;
        }

        for(i=0;i<n;i++)//因为点小怕凸包会有bug 就特殊处理了.
        {
            if(a[i]==max&&my2[make_pair(x[i],y[i])]==1)//my2看是不是重点
                printf("1");
            else
                printf("0");
        }
        puts("");
    }
    return 0;
}


/*代码打得丑,但是数据送的多呀,哈哈
4
1 1 3
2 2 3
0 0 3
1 2 3
//1111

4
1 1 3
1 1 3
2 2 3
3 3 3
//0011

3
0 0 3
1 1 2
2 2 1
//100

8
1 1 3
1 2 3
2 2 3
2 1 3
2 1 3
3 3 3
3 3 3
2 2 2
//11000000

4
-1 -1 3
1 1 3
1 -1 3
-1 1 3
//1111


10
1 1 3
1 1 3
1 1 3
1 1 3
1 1 3
1 1 3
1 1 3
1 1 3
1 1 3
0 0 3
000000001
*/