链接：http://acm.hdu.edu.cn/showproblem.php?pid=4946
题意：有n个人，在位置（xi,yi），速度是vi，如果对于某个点一个人比所有其他的都能先到那个点，那这个点就被这个人承包了。输出有多少人承包的（鱼塘）面积是无穷大。
思路：找出速度最大值，只有速度是这个最大值的人才有可能承包无穷大的面积（因为高速者早晚会追上低速者）。每两个人相比，他们能承包的位置的界线是他们坐标的中垂线，可以证明的是，在组成凸包时，在凸包里的人，承包的面积一定是有限的。所以在凸包上的人（包括边上）才可能承包无穷大的面积。注意点在于由于题里要求严格小于其他人到达的时间才能承包，所以如果出现重点重速的两个人，那么两个人都是不能承包的，但是在计算凸包时它们需要计进来因为有可能因为他们的存在导致其他人承包不了。
代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-10
#define INF 0x7fffffff
#define maxn 10005
#define PI acos(-1.0)
#define seed 31//131,1313
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
int x[505],y[505],v[505],vis[505];
int cmp(double x)
{
if(fabs(x)<eps)
return 0;
if(x>0)
return 1;
return -1;
}
inline double sqr(double x)
{
return x*x;
}
struct point//点
{
double x,y;
int pos;
int o;
point() {}
point(double a,double b):x(a),y(b) {}
void input()
{
scanf("%lf%lf",&x,&y);
}
friend point operator + (const point &a,const point &b)
{
return point(a.x+b.x,a.y+b.y);
}
friend point operator - (const point &a,const point &b)
{
return point(a.x-b.x,a.y-b.y);
}
friend bool operator == (const point &a,const point &b)
{
return cmp(a.x-b.x)==0 &&cmp(a.y-b.y)==0;
}
friend point operator * (const point &a,const double &b)
{
return point(a.x*b,a.y*b);
}
friend point operator * (const double &a,const point &b)
{
return point(a*b.x,a*b.y);
}
friend point operator / (const point &a,const double &b)
{
return point(a.x/b,a.y/b);
}
double norm()
{
return sqrt(sqr(x)+sqr(y));
}//到原点距离
void out () const
{
printf("%.2f %.2f",x,y);
}
} p[505];
double det (const point &a,const point &b)
{
return a.x*b.y-a.y*b.x;
}//叉积
double dot (const point &a,const point &b)
{
return a.x*b.x+a.y*b.y;
}//点乘
double dist (const point &a,const point &b)
{
return (a-b).norm();
}//距离
point rotate_point(const point &p,double A)
{
double tx=p.x,ty=p.y;
return point (tx*cos(A)-ty*sin(A),tx*sin(A)+ty*cos(A));
}//旋转，A是弧度
struct polygon_convex
{
vector <point> P;
polygon_convex(int size=0)
{
P.resize(size);
}
} p_c;
bool comp_less(const point &a,const point &b)
{
return cmp(a.x-b.x)<0||cmp(a.x-b.x)==0&&cmp(a.y-b.y)<0;
}
polygon_convex convex_hull(vector <point> a)
{
polygon_convex res(2*a.size()+5);
sort(a.begin(),a.end(),comp_less);
a.erase(unique(a.begin(),a.end()),a.end());
int m=0;
for(int i=0; i<a.size(); i++)
{
while(m>1 && cmp(det(res.P[m-1]-res.P[m-2],a[i]-res.P[m-2]))<0)
m--;
res.P[m++]=a[i];
}
int k=m;
for(int i=int(a.size())-2; i>=0; i--)
{
while(m>k && cmp(det(res.P[m-1]-res.P[m-2],a[i]-res.P[m-2]))<0)
m--;
res.P[m++]=a[i];
}
res.P.resize(m);
if(a.size()>1)
res.P.resize(m-1);
return res;
}
bool cmp3(point a,point b)
{
return a.x<b.x||((a.x==b.x)&&(a.y<b.y));
}
int main()
{
int T,tt=0;
while(scanf("%d",&T))
{
tt++;
vector<point>pp;
pp.clear();
memset(vis,0,sizeof(vis));
if(T==0)
break;
int pos=-1;
int max_v=0;
for(int i=1; i<=T; i++)
{
scanf("%d%d%d",&x[i],&y[i],&v[i]);
if(v[i]>max_v)
max_v=v[i];
}
int top=0;
for(int i=1; i<=T; i++)
{
if(v[i]==max_v)
{
p[top].x=(double)x[i];
p[top].y=(double)y[i];
p[top].pos=i;
p[top].o=0;
top++;
}
}
printf("Case #%d: ",tt);
if(max_v==0)
{
for(int i=1; i<=T; i++)
printf("0");
printf("\n");
continue;
}
sort(p,p+top,cmp3);
for(int i=0; i<top; i++)
{
if((i<top-1&&(p[i].x)==(p[i+1].x)&&(p[i].y)==(p[i+1].y))||(i>0&&(p[i].x)==(p[i-1].x)&&(p[i].y)==(p[i-1].y)))
p[i].o=1;
}
pp.push_back(p[0]);
for(int i=1; i<top; i++)
{
if(p[i].x!=p[i-1].x||p[i].y!=p[i-1].y)
pp.push_back(p[i]);
}
if(pp.size()<=3)
{
for(int i=0; i<pp.size(); i++)
if(pp[i].o==0)
vis[pp[i].pos]=1;
}
else
{
polygon_convex ans=convex_hull(pp);
for(int i=0; i<ans.P.size(); i++)
{
if(ans.P[i].o==0)
vis[ans.P[i].pos]=1;
}
}
for(int i=1; i<=T; i++)
printf("%d",vis[i]);
printf("\n");
}
return 0;
}