题意：
对于一张没有边界的二维图。给定n个点，每个点有一个学生，其坐标为(xi,yi)，具有一个速度vi。对于一个点(x,y)，若有一个学生j能到达，且比其他学生都先到达（走直线），那么这个点就是学生j的管辖范围。现在要判断各个学生的管辖区域的面积是否是无限的。输出一行表示管辖情况，若第i个学生管辖范围无限则第i位输出1，否则输出0。
题解：
先根据速度排序，比最大速度小的学生的管辖范围都不是无限的，因为每个学生的范围都是以圆的方式向外拓展，更大的速度的学生的管辖范围在一定时间后覆盖掉速度小。
之后求拥有最大速度的学生的凸包。在凸包上的点必定管辖距离无限（除非这个点有多个速度最大的学生），在凸包内的点肯定管辖范围有限，这个容易理解。
之后就是排除特殊的情况：
1）最大速度为0的情况，那么肯定都是有限，即使只有一个点的情况也不能，因为题意表示要使一个点是一个学生的管辖范围，那个学生必须能够达到。
2）速度相等，且速度为最大速度，且位置相等的情况。这样的点肯定是范围有限的，因为题意中要求管辖范围必须是严格小于其他学生。
注意：
1）求凸包的时候需要考虑凸包边上的点，可以再求出正常的凸包后，枚举所有最大速度点，判断是否在凸包上。但不能直接将叉积判断Cross()从<=改成<，因为如果存在共点在凸包内的情况，会让求出的凸包的凹的；即使去掉共点的情况下，还要注意所有点在一条线上的时候，凸包长度会*2，小心数组越界。
代码：
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <iomanip>
using namespace std;
const int maxn=505;
struct Point{
int x,y,v,id,flag,vis;
Point(int x=0,int y=0):x(x),y(y){}
}e[maxn],p[maxn],ch[maxn];
typedef Point Vector;
Vector operator - (Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}
int Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}//叉积
int cmp1(Point a,Point b)
{
if(a.v==b.v)return a.x<b.x||(a.x==b.x&&a.y<b.y);
return a.v>b.v;
}
int cmp2(Point a,Point b)
{
return a.id<b.id;
}
int ConvexHull(Point *p,Point *ch,int n)//求凸包
{
//sort(p,p+n,cmp3);
int i,m=0,k;
for(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];
}
k=m;
for(i=n-2;i>=0;i--)
{
//cout<<"*"<<m<<endl;
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()
{
//freopen("D:\\in.txt","r",stdin);
int n,tt=0;
while(scanf("%d",&n)!=EOF)
{
if(n==0)break;
int i,j,k,t,m;
for(i=0;i<n;i++)
{
scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].v);
e[i].id=i;
e[i].flag=0;
e[i].vis=0;
}
sort(e,e+n,cmp1);
for(i=1;i<n;i++)
{
if(e[i].v!=e[i-1].v)break;
if(e[i].x==e[i-1].x&&e[i].y==e[i-1].y)e[i].vis=e[i-1].vis=1;
}
t=i;
for(i=0;i<t;i++)
{
p[i]=e[i];
}
if(e[0].v==0)t=0;
m=ConvexHull(p,ch,t);
for(i=0;i<t;i++)
{
for(j=0;j<m;j++)
{
if(Cross(ch[j]-ch[(j+1)%m],ch[j]-e[i])==0)
{
if(!e[i].vis)//该点没有与之重合且速度相同的点
e[i].flag=1;
break;
}
}
}
sort(e,e+n,cmp2);
printf("Case #%d: ",++tt);
for(i=0;i<n;i++)printf("%d",e[i].flag);
printf("\n");
}
return 0;
}
/*
5
0 0 1
1 0 1
0 1 1
1 1 1
2 0 1
3
0 0 0
1 1 0
2 2 0
9
0 0 1
1 0 1
2 0 1
0 1 1
1 1 2
2 1 1
0 2 1
1 2 1
2 2 1
ans:
11111
000
000010000
*/
