思路： 只有速度最大才有可能为1，速度不是最大肯定为0，那么就是 只需要操作那些速度最大的点，这些点求一个凸包，判断一下是不是在凸包边上即可。
有几个需要注意的地方：
1.最大速度如果为0 那么肯定所有都不行。
2.如果最大速度有重点那么 也都不行。
3.有些求凸包模板求出来的凸包可能有重点，要去重再求。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include <iostream> #define EPS 1e-8 #define eps 1e-8 using namespace std; struct TPoint { double x,y; int id,v; }p[510],s[506],hull[510],pp[510]; double cross(TPoint a, TPoint b, TPoint c) { return (b.x - a.x) * (c.y - a.y) - (c.x - a.x)*(b.y - a.y); } double dis(TPoint a,TPoint b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } bool graham_cmp(const TPoint &b, const TPoint &c) { double tmp = cross(b, c, p[0]); if (tmp > EPS) return true; if (fabs(tmp) < EPS && (dis(b, p[0]) < dis(c, p[0]))) return true; return false; } int graham_scan(TPoint hull[], int n) { int top, i, k = 0; for (i = 1; i < n; ++i) if ((p[k].y - p[i].y > EPS) || (fabs(p[i].y - p[k].y) < EPS && p[k].x - p[i].x > EPS)) k = i; swap(p[0], p[k]); sort(p + 1, p + n, graham_cmp); hull[0] = p[0], hull[1] = p[1], hull[2] = p[2]; if (n < 3) return n; else top = 3; for (i = 3; i < n; ++i) { while (top >= 2 && cross(hull[top - 2], hull[top - 1], p[i]) < EPS) --top; hull[top++] = p[i]; } return top; } bool bo[550]; int ans[550]; bool cmp(TPoint a,TPoint b) { return a.x<b.x-eps||(fabs(a.x-b.x)<eps&&a.y<b.y); } int main() { int ri=0,n; while(scanf("%d",&n)&&n) { int maxn=0; for(int i=0;i<n;++i) ans[i]=0; for(int i=0;i<n;++i) { scanf("%lf%lf%d",&s[i].x,&s[i].y,&s[i].v); s[i].id=i; maxn=std::max(maxn,s[i].v); } if(maxn==0) { printf("Case #%d: ",++ri); for(int i=0;i<n;++i) printf("0"); puts(""); continue; } int tail=0; for(int i=0;i<n;++i) { if(s[i].v==maxn&&maxn>0) { pp[tail]=s[i]; p[tail++]=s[i]; } } sort(p,p+tail,cmp); int kk=0; for(int i=0;i<tail;++i) if(i==tail-1||fabs(p[i].x-p[i+1].x)>eps||fabs(p[i].y-p[i+1].y)>eps) p[kk++]=p[i]; int h=graham_scan(hull,kk); hull[h]=hull[0]; for(int i=0;i<tail;++i) { int flag=0; for(int j=0;j<tail;++j) if(i!=j&&fabs(pp[i].x-pp[j].x)<eps&&fabs(pp[i].y-pp[j].y)<eps) { flag=1; break; } if(flag) { ans[pp[i].id]=0; continue; } bool ok=false; for(int j=0;j<h;++j) { if(fabs(cross(pp[i],hull[j],hull[j+1]))<eps) ok=true; } if(ok) ans[pp[i].id]=1; else ans[pp[i].id]=0; } printf("Case #%d: ",++ri); for(int i=0;i<n;++i) printf("%d",ans[i]); puts(""); } }