HDU 4946 Area of Mushroom 求凸包边上的点

时间：2022-05-26 20:53:55

Area of Mushroom

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

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 
 
  

    30 0 31 1 22 2 10 
  
 
 
 
 

     
 
 
 

   Sample Output 
 
 
 
 
  
 
  

    Case #1: 100 
  
 
 
 
 

     
 
 
 

   Source 
 
 
 
 
  2014 Multi-University Training Contest 8 
 
 
 

     
 
 
 
 
  


 
 给你n个点的坐标和速度，如果一个点能够到达无穷远处，且花费的时间是最少的，则此点输出1，否则输出0. 

 

 
 每个点向外都是以园的形式向外拓展的，所以只有速度最大的才能到达无穷远处，但是并不是所有速度为最大的点都能到到无穷远处。 

 

 
 将速度最大的所有点做一个凸包，凸包内的点肯定不能到达无穷远处，凸包上的点才满足条件。 




 
 
//109MS	292K
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
struct Point
{
    int x,y,k,id,vis,flag;
    Point(int x=0,int y=0):x(x),y(y) {} //构造函数
};
typedef Point Vector;
Point operator-(Point A,Point B)
{
    return Point(A.x-B.x,A.y-B.y);
}
int Cross(Point A,Point B)
{
    return A.x*B.y-A.y*B.x;
}
int cmp1(Point a,Point b)
{
    if(a.k==b.k)
    {
        if(a.x==b.x)return a.y<b.y;
        return a.x<b.x;
    }

    return a.k>b.k;
}
int cmp2(Point a,Point b)
{
    return a.id<b.id;
}

int ConvexHull(Point* p,int n,Point* ch)//求凸包
{
    int m=0;
    for(int i=0;i<n;i++)
    {
        while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
        ch[m++]=p[i];
    }
    int k=m;
    for(int i=n-2;i>=0;i--)
    {
        while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
        ch[m++]=p[i];
    }
    if(n>1)m--;
    return m;
}

int main()
{
        int n,cas=1;
        while(scanf("%d",&n),n)
        {
            Point P[507],ch[507],v[507];
            int i;
            for(i=0; i<n; i++)
            {
                scanf("%d%d%d",&P[i].x,&P[i].y,&P[i].k);
                P[i].id=i;P[i].vis=P[i].flag=0;
            }
            sort(P,P+n,cmp1);
            v[0]=P[0];
            for(i=1;i<n;i++)
                if(P[i].k!=P[i-1].k)break;
                else
                {
                    v[i]=P[i];
                    if(P[i].x==P[i-1].x&&P[i].y==P[i-1].y)P[i].vis=v[i].vis=P[i-1].vis=v[i-1].vis=1;
                }
            int num=i;
            int m=ConvexHull(v,num,ch);
            if(P[0].k==0)num=0;
            for(i=0;i<num;i++)
                for(int j=0;j<m;j++)
                    if(Cross(ch[j]-ch[(j+1)%m],ch[j]-P[i])==0)
                    {
                        if(!P[i].vis)P[i].flag=1;
                        break;
                    }
            sort(P,P+n,cmp2);
            printf("Case #%d: ",cas++);
            for(int i=0;i<n;i++)
                printf("%d",P[i].flag);
            printf("\n");
        }
    return 0;
}
 
 



标签：
相关文章