思路: 只有速度最大才有可能为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[],s[],hull[],pp[];
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[]);
if (tmp > EPS)
return true;
if (fabs(tmp) < EPS && (dis(b, p[]) < dis(c, p[])))
return true;
return false;
}
int graham_scan(TPoint hull[], int n) {
int top, i, k = ;
for (i = ; 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[], p[k]);
sort(p + , p + n, graham_cmp);
hull[] = p[], hull[] = p[], hull[] = p[];
if (n < )
return n;
else
top = ;
for (i = ; i < n; ++i) {
while (top >= && cross(hull[top - ], hull[top - ], p[i]) < EPS)
--top;
hull[top++] = p[i];
}
return top;
}
bool bo[];
int ans[];
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=,n;
while(scanf("%d",&n)&&n)
{
int maxn=;
for(int i=;i<n;++i)
ans[i]=;
for(int i=;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==)
{
printf("Case #%d: ",++ri);
for(int i=;i<n;++i)
printf("");
puts("");
continue;
}
int tail=;
for(int i=;i<n;++i)
{
if(s[i].v==maxn&&maxn>)
{
pp[tail]=s[i];
p[tail++]=s[i];
}
}
sort(p,p+tail,cmp);
int kk=;
for(int i=;i<tail;++i)
if(i==tail-||fabs(p[i].x-p[i+].x)>eps||fabs(p[i].y-p[i+].y)>eps)
p[kk++]=p[i];
int h=graham_scan(hull,kk);
hull[h]=hull[];
for(int i=;i<tail;++i)
{
int flag=;
for(int j=;j<tail;++j)
if(i!=j&&fabs(pp[i].x-pp[j].x)<eps&&fabs(pp[i].y-pp[j].y)<eps)
{
flag=;
break;
}
if(flag)
{
ans[pp[i].id]=;
continue;
}
bool ok=false;
for(int j=;j<h;++j)
{
if(fabs(cross(pp[i],hull[j],hull[j+]))<eps)
ok=true;
}
if(ok)
ans[pp[i].id]=;
else
ans[pp[i].id]=;
}
printf("Case #%d: ",++ri);
for(int i=;i<n;++i)
printf("%d",ans[i]);
puts(""); }
}