大致题意:
平面上有n个人，给你每个人的坐标和一个速度v，如果某个人比其他所有人都先到达某点，则该点就被这个人掌控，求谁掌控者无限大的面积。
首先 速度最大的人，抛弃其他人，速度小的人必定无法得到无限的面积。
然后 所有速度最大的人建凸包，则凸包上节点的人和凸包边上的人必定有无限的面积，凸包内部的人必定没有，因为速度都相等。
ps：建凸包时不能直接将叉积的<=该为<来构建边上有点的凸包，因为有重点。
最后将所有得到的人中有重合的全部去除，最后留下的人掌控的面积无限
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<map> #include<stack> #include<time.h> #include<cstdlib> #include<cmath> #include<list> using namespace std; #define MAXN 100100 #define eps 1e-9 #define For(i,a,b) for(int i=a;i<=b;i++) #define Fore(i,a,b) for(int i=a;i>=b;i--) #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define mkp make_pair #define pb push_back #define cr clear() #define sz size() #define met(a,b) memset(a,b,sizeof(a)) #define iossy ios::sync_with_stdio(false) #define fre freopen #define pi acos(-1.0) #define inf 1e6+7 #define Vector Point const int Mod=1e9+7; typedef unsigned long long ull; typedef long long ll; int dcmp(double x){ if(fabs(x)<=eps) return 0; return x<0?-1:1; } struct Point{ double x,y; int v; int id; Point(double x=0,double y=0):x(x),y(y) {} bool operator < (const Point &a)const{ if(x==a.x && y==a.y) return v<a.v; if(x==a.x) return y<a.y; return x<a.x; } Point operator - (const Point &a)const{ return Point(x-a.x,y-a.y); } Point operator + (const Point &a)const{ return Point(x+a.x,y+a.y); } Point operator * (const double &a)const{ return Point(x*a,y*a); } Point operator / (const double &a)const{ return Point(x/a,y/a); } void read(){ scanf("%lf%lf",&x,&y); scanf("%d",&v); } void out(){ cout<<"debug: "<<x<<" "<<y<<endl; } bool operator == (const Point &a)const{ return dcmp(x-a.x)==0 && dcmp(y-a.y)==0; } bool operator !=(const Point &a)const{ return dcmp(x-a.x)!=0 || dcmp(y-a.y)!=0; } }; double Dot(Vector a,Vector b) { return a.x*b.x+a.y*b.y; } double dis(Vector a) { return Dot(a,a); } double Cross(Point a,Point b){ return a.x*b.y-a.y*b.x; } bool cmp(Point a,Point b){ if(a.x==b.x) return a.y<b.y; return a.x<b.x; } int vt[5005]; int ConvexHull(Point *p,int n,Point *ch,int maxv){ sort(p,p+n,cmp); 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 n; Point p[5005]; Point ch[5005]; Point pp[5005]; char s[5005]; void solve(){ met(vt,0); int maxv=0; s[n]='\0'; int rt=0; For(i,0,n-1) s[i]='0'; For(i,0,n-1) p[i].read(),p[i].id=i; sort(p,p+n); For(i,1,n-1) { if(p[i]==p[i-1] && p[i].v==p[i-1].v) vt[p[i].id]=1,vt[p[i-1].id]=1; } For(i,0,n-1) maxv=max(maxv,p[i].v); For(i,0,n-1) if(p[i].v==maxv) pp[rt++]=p[i]; if(maxv==0){ puts(s); return ; } int m=ConvexHull(pp,rt,ch,maxv); For(i,0,m-1){ if(!vt[ch[i].id]) s[ch[i].id]='1'; } For(i,0,rt-1) { // cout<<"Bug: "<<pp[i].id<<" "<<vt[pp[i].id]<<endl; // pp[i].out(); For(j,0,m-1){ if(dcmp(Cross(ch[j]-pp[i],ch[(j+1)%m]-pp[i]))==0 && !vt[pp[i].id]) {s[pp[i].id]='1';break;} } } puts(s); } int main(){ // fre("in.txt","r",stdin); int t=0; while(~scanf("%d",&n) && n) printf("Case #%d: ",++t),solve(); return 0; }