题意：
在二维平面上，给定n个人
每个人的坐标和移动速度v
若对于某个点，只有 x 能最先到达（即没有人能比x先到这个点或者同时到这个点）
则这个点称作被x占有，若有人能占有无穷大的面积 则输出1 ，否则输出0
思路：
1、把所有点按速度排个序，然后把不是最大速度的点去掉
剩下的点才有可能是占有无穷大的面积
2、给速度最大的点做个凸包，则只有在凸包上的点才有可能占有无穷大
若一个位置有多个人，则这几个人都是不能占有无穷大的。
凸包上边里共线的点是要保留的。
#易错点：
1.凸包边上要保留共线的点，最好采用水平排序（构造凸包前）
2.对于去重点，必须在构造完凸包之后。
WA：构造凸包之前去重点（构造凸包的点不包括有重复的点）
#include<stdio.h>
#include<algorithm>
#include<fstream>
#include<string.h>
#include<iostream>
using namespace std;
const int MAX=;
struct point
{
int x;
int y;
int v;
int i;
}p[MAX],Ini[MAX],res[MAX];
int ans[MAX];
bool cmp(point A,point B)
{
if(A.y==B.y)return A.x<B.x;
return A.y<B.y;
}
bool cmp1(point A,point B)
{
if(A.v>B.v)return true;
if(A.v==B.v)
{
if(A.x<B.x)return true;
if(A.x==B.x&&A.y<B.y)return true;
}
return false;
}
int cross(point A,point B,point C)
{
return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
}
int Graham(point *p,int n)
{
//if (n<3)return n;
sort(p,p+n,cmp);
int i;
int top=;
for(i=;i<n;i++)
{
while(top>=&&cross(res[top-],res[top-],p[i])<)
top--;
res[top++]=p[i];
}
int t=top+;
for(i=n-;i>=;i--)
{
while(top>=t&&cross(res[top-],res[top-],p[i])<)
top--;
res[top++]=p[i];
}
/*for(i=0;i<top;i++)
printf("%d %d\n",res[i].x,res[i].y);*/
return top;
}
int main()
{
int n;
int i,j;
//ifstream cin("A.txt");
int __case=;
while(cin>>n&&n)
{
for(i=;i<n;i++)
{
cin>>Ini[i].x>>Ini[i].y>>Ini[i].v;
Ini[i].i=i;
}
sort(Ini,Ini+n,cmp1);
//cout<<Ini[i-1].x<<Ini[i-1].y;
int tmp=;
for(i=;i<n;i++)
{
if(Ini[].v==Ini[i].v)tmp++;
else break;
}
point po;
for(i=,j=;i<tmp;)
{
po=Ini[i];
if(i<tmp-&&Ini[i+].x==Ini[i].x&&Ini[i+].y==Ini[i].y)
{
while(i<tmp-&&Ini[i+].x==Ini[i].x&&Ini[i+].y==Ini[i].y)
i++;
}
else
{
p[j++]=po;
}
i++;
}
printf("Case #%d: ",++__case); int m=Graham(p,j); memset(ans,,sizeof(ans));
for(i=;i<m;i++)
{
//printf("%d %d %d",res[i].x,res[i].y,res[i].v);
if(res[i].v>)
{
ans[res[i].i]=;
}
}
for(i=;i<n;i++)
printf("%d",ans[i]);
printf("\n");
}
return ;
}
WA：构造凸包之后去重点
#include<stdio.h>
#include<algorithm>
#include<fstream>
#include<string.h>
#include<iostream>
using namespace std;
const int MAX=;
struct point
{
int x;
int y;
int v;
int i;
int tmp;
} Ini[MAX],res[MAX];
bool flag[MAX];
int ans[MAX];
bool cmp(point A,point B)
{
if(A.y==B.y)return A.x<B.x;
return A.y<B.y;
}
bool cmp1(point A,point B)
{
if(A.v>B.v)return true;
return false;
}
int cross(point A,point B,point C)
{
return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
}
int Graham(point *p,int n)
{
//if (n<3)return n;
sort(p,p+n,cmp);
memset(flag,false,sizeof(flag));
int i;
int top=;
for(i=; i<n; i++)
{
while(top>=&&cross(res[top-],res[top-],p[i])<)
top--; res[top++]=p[i];
res[top-].tmp=i;
}
for(i=;i<top;i++)
flag[res[i].tmp]=true; int t=top+;
for(i=n-; i>=; i--) //i>=0
{
while(top>=t&&cross(res[top-],res[top-],p[i])<)
top--;
if(!flag[i])res[top++]=p[i];
//if(i==0)top--;
}
/*for(i=0; i<top; i++)
printf("$%d %d\n",res[i].x,res[i].y);*/
return top;
}
int main()
{
int n;
int i,j;
//ifstream cin("A.txt");
int __case=;
while(cin>>n&&n)
{
for(i=; i<n; i++)
{
cin>>Ini[i].x>>Ini[i].y>>Ini[i].v;
Ini[i].i=i;
}
sort(Ini,Ini+n,cmp1);
//cout<<Ini[i-1].x<<Ini[i-1].y;
int tmp=;
for(i=; i<n; i++)
{
if(Ini[].v>&&Ini[].v==Ini[i].v)tmp++;
else break;
}
int m=Graham(Ini,tmp);
memset(ans,,sizeof(ans));
printf("Case #%d: ",++__case);
point po;
for(i=; i<m; i++)
{
po=res[i];
//printf("#%d %d %d\n",res[i].x,res[i].y,res[i].i);
if(i<m-&&res[i+].x==po.x&&res[i+].y==po.y)
{
while(i<m-&&res[i+].x==po.x&&res[i+].y==po.y)
i++;
}
else
ans[po.i]=;
}
for(i=; i<n; i++)
printf("%d",ans[i]);
printf("\n");
}
return ;
}
数据：
构造凸包之前去掉重点，保留相同点中的一个。
AC：
#include<stdio.h>
#include<algorithm>
#include<fstream>
#include<string.h>
#include<iostream>
using namespace std;
const int MAX=;
struct point
{
int x;
int y;
int v;
int i;
int tmp;
} Ini[MAX],res[MAX],p[MAX];
bool flag[MAX];
int ans[MAX];
bool cmp(point A,point B)
{
if(A.y==B.y)return A.x<B.x;
return A.y<B.y;
}
bool cmp1(point A,point B)
{
if(A.v>B.v)return true;
if(A.v==B.v)
{
if(A.x<B.x)return true;
if(A.x==B.x&&A.y<B.y)return true;
}
return false;
}
int cross(point A,point B,point C)
{
return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
}
int Graham(point *p,int n)
{
//if (n<3)return n;
sort(p,p+n,cmp);
memset(flag,false,sizeof(flag));
int i;
int top=;
for(i=; i<n; i++)
{
while(top>=&&cross(res[top-],res[top-],p[i])<)
{
top--;
}
res[top++]=p[i];
res[top-].tmp=i;
}
for(i=;i<top;i++)
flag[res[i].tmp]=true; int t=top+;
for(i=n-; i>=; i--) //i>=0
{
while(top>=t&&cross(res[top-],res[top-],p[i])<)
top--;
if(!flag[i])res[top++]=p[i];
//if(i==0)top--;
}
/*for(i=0; i<top; i++)
printf("$%d %d\n",res[i].x,res[i].y);*/
return top;
}
int main()
{
int n;
int i,j;
//ifstream cin("A.txt");
int __case=;
while(cin>>n&&n)
{
for(i=; i<n; i++)
{
cin>>Ini[i].x>>Ini[i].y>>Ini[i].v;
Ini[i].i=i;
}
sort(Ini,Ini+n,cmp1);
//cout<<Ini[i-1].x<<Ini[i-1].y;
int tmp=;
for(i=; i<n; i++)
{
if(Ini[].v>&&Ini[].v==Ini[i].v)tmp++;
else break;
} memset(ans,,sizeof(ans));
point po;
for(i=,j=;i<tmp;i++)
{
po=Ini[i];
//flag=1;
if(i<tmp-&&Ini[i+].x==po.x&&Ini[i+].y==po.y)
{
//flag=0;
while(i<tmp-&&Ini[i+].x==po.x&&Ini[i+].y==po.y)
{
ans[Ini[i].i]=-;
i++;
}
ans[Ini[i].i]=-;
}
p[j++]=po;
}
int m=Graham(p,j); printf("Case #%d: ",++__case);
for(i=; i<m; i++)
{
if(!ans[res[i].i])ans[res[i].i]=;
}
for(i=; i<n; i++)
{
if(ans[i]==)printf("");
else printf("");
}
printf("\n");
}
return ;
}