题意：给定n个人，每个人有一个速度v方向任意。如果平面中存在一个点只有某个人到达的时间最短(即没有人比这个人到的时间更短或相同)，那么我们定义这个店归这个人管辖，现在问这些人中哪些人的管辖范围是无限的，无限的输出1，否则输出0。
题解：这道题错了好多遍TOT，首先我们从速度角度考虑，速度不是最大值的人管辖范围一定有限为0，所以我们只需要考虑速度最大值的人即可，如果速度最大值为0要特判一下。所以我们对于这些人先求一个凸包，再来研究这个凸包：
这个题有很多坑，首先在凸包边上的人也要考虑进去，但是要注意只考虑速度为最大值的人，因为他们的管辖范围也是无限的，先把凸包求出来再用叉积遍历速度最大值的人，注意在这个遍历过程要循环遍历即不能丢了0和num-1这条边。还有人也可能重合，有可能两个速度为最大值的人站在凸包的一个点上，但是算凸包之前不能直接删去因为会影响凸包，边上的也要考虑，所以要用flag=1标记一下他们最后再把他们的结果标为0。求凸包之前先标记一下每个点的标记为i，最后算结果的时候注意嵌套数组一定注意算的是id而不是i。还要注意所有点在一条线上的时候，凸包长度会*2，小心数组越界RE，所以把数组开大一点好。在求凸包过程中不能把<=改为<来求边上的人，这样是不对的。
不能从<=改为<的原因：
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
struct Point{
double x,y;
int id,v,flag;
Point(double x=,double y=,int id=-,int v=-,int flag=-):x(x),y(y),id(id),v(v),flag(flag){}
};
typedef Point Vector;
Vector operator + (Vector A,Vector B)
{
return Vector(A.x+B.x,A.y+B.y);
}
Vector operator - (Point A,Point B)
{
return Vector(A.x-B.x,A.y-B.y);
}
Vector operator * (Vector A,double p)
{
return Vector(A.x*p,A.y*p);
}
Vector operator / (Vector A,double p)
{
return Vector(A.x/p,A.y/p);
}
bool operator <(const Point &a,const Point &b)
{
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
const double eps=1e-;
int dcmp(double x)
{
if(fabs(x)<eps) return ; else return x<?-:;
}
bool operator ==(const Point &a,const Point &b)
{
return dcmp(a.x-b.x)==&&dcmp(a.y-b.y)==;
}
double Cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
int ConvexHull(Point *p,int n,Point* ch)
{
sort(p,p+n);
int m=;
for(int i=;i<n;i++)
{
while(m>&&Cross(ch[m-]-ch[m-],p[i]-ch[m-])<=) m--;
ch[m++]=p[i];
}
int k=m;
for(int i=n-;i>=;i--)
{
while(m>k&&Cross(ch[m-]-ch[m-],p[i]-ch[m-])<=) m--;
ch[m++]=p[i];
}
if(n>) m--;
return m;
}
int main()
{
int n,m,cas=;
while(scanf("%d",&m)&&m)
{
Point p[],ch[];
int mx=-;
memset(p,,sizeof(p));
memset(ch,,sizeof(ch));
for(int i=;i<m;i++)
{
scanf("%lf%lf%d",&p[i].x,&p[i].y,&p[i].v);
p[i].id=i;
p[i].flag=-;//flag
mx=max(mx,p[i].v);
}
//也可以sort排序做
for(int i=;i<m;i++)
for(int j=i+;j<m;j++)
if((p[i].x==p[j].x)&&(p[i].y==p[j].y)&&(p[i].v==p[j].v))
{
p[i].flag=;
p[j].flag=;
}
if(mx==)
{
printf("Case #%d: ",cas++);
for(int i=;i<m;i++)
printf("");
printf("\n");
continue;
}
int cnt=;
for(int i=;i<m;i++)
{
if(p[i].v==mx)
{
ch[cnt++]=p[i];
}
}
Point ans[];
memset(ans,,sizeof(ans));
int num=ConvexHull(ch,cnt,ans);
//cout<<num<<endl;
int num2=;
Point ans2[];
int a1[];
memset(a1,,sizeof(a1));
for(int i=;i<cnt;i++) //
for(int j=;j<num;j++) //
if(Cross(ans[j]-ans[(j+)%num],ans[j]-ch[i])==) //这里用j+1更好因为可以取余
{
//如果在凸包上或凸包边上而且不重复
//不必先把边上的点先求出来
if(p[ch[i].id].flag==-)
a1[ch[i].id]=;
}
printf("Case #%d: ",cas++);
for(int i=;i<m;i++)
printf("%d",a1[i]);
printf("\n");
}
return ;
}
/*
3
0 0 3
1 1 3
2 2 3
*/