题目链接：Area of Mushroom
题意：有一些同学站在二维平面上，每个同学有个速度。平面上的点归第一个到达的同学所有。如果一个同学能到达的点是无穷的是1，否则为0。
题解：找出速度最大的点，求凸包。
1、最大速度为零，所有同学都只能到达有限的点。
2、两个同学在同一个点，速度相同。只能到达有限个点。
代码：
//一开始各种wa,不到错哪了，后来给求凸包是叉积判 <= 改成 < 过了。不是很明白
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <string>
using namespace std;
#define For(i,a) for(i=0;i<a;i++)
#define Foru(i,a,b) for(i=a;i<=b;i++)
#define Ford(i,a,b) for(i=a;i>=b;i--)
#define clr(ar,vel) memset(ar,vel,sizeof(ar))
#define PB push_back
typedef long long ll;
const int maxint = 0x7fffffff;
const ll maxll = 1LL<<60;
const double EPS = 1e-10;
// 二维向量类
double add( double a, double b){
if( abs(a+b) < EPS * ( abs(a) + abs(b))) return 0;
return a+b;
}
struct P{
double x, y;
int num;
P() {}
P(double x, double y) : x(x), y(y) {}
P operator + (P p){ return P(add(x, p.x), add(y, p.y));}
P operator - (P p){ return P(add(x, -p.x), add(y, -p.y));}
P operator * (double d){ return P(x*d, y*d);}
bool operator < (const P& a) const {
if( x != a.x) return x < a.x;
else return y < a.y;
}
double dot(P p){ return add(x*p.x, y*p.y);}
double det(P p) { return add( x*p.y, -y*p.x);}
};
P p[50010];
int n;
vector<P> convex_hull(P *ps, int n){
sort(p, p+n);
int k = 0;
vector<P> qs(n*2);
// down
for(int i = 0; i < n; i ++){
while( k > 1 && (qs[k-1] - qs[k-2]).det(ps[i] - qs[k-1]) < 0) k--;
qs[k++] = ps[i];
}
// up
for(int i = n-2, t = k; i >= 0; i --){
while( k > t && (qs[k-1] - qs[k-2]).det(ps[i] - qs[k-1]) < 0) k--;
qs[k++] = ps[i];
}
qs.resize(k-1);
return qs;
}
double dist(P p, P q){
return (p-q).dot(p-q);
}
struct node {
int x, y, vel;
void scan(){ scanf("%d%d%d",&x,&y,&vel);}
}node[510];
int ans[510], vis[510];
int main(){
int cas = 1;
while(~scanf("%d",&n)) {
if( n == 0 ) break;
int max_speed = 0, cnt = 0;
memset( ans, 0, sizeof(ans));
memset( vis, 0, sizeof(vis));
for(int i = 0; i < n; i ++) {
node[i].scan();
max_speed = max(max_speed, node[i].vel);
}
if( max_speed == 0 ) {
printf("Case #%d: ",cas++);
for(int i = 0; i < n; i ++) printf("%d",ans[i]);
printf("\n");
continue;
}
for(int i = 0; i < n; i ++){
for(int j = 0; j < n; j ++){
if( node[i].x == node[j].x && node[i].y == node[j].y && node[i].vel == node[j].vel && i != j) vis[i] = vis[j] = 1;
}
}
for(int i = 0; i < n; i ++) if( node[i].vel == max_speed){
int flag = 0;
for(int j = 0; j < i; j ++){
if( node[i].x == node[j].x && node[i].y == node[j].y && node[i].vel == node[j].vel && i != j) flag = 1;
}
if( flag ) continue;
p[cnt].x = node[i].x;
p[cnt].num = i;
p[cnt++].y = node[i].y;
}
// for(int i = 0; i < cnt; i ++) cout << p[i].num << ' ' ;cout << endl;
if( cnt != 1 && max_speed != 0) {
vector<P> qs = convex_hull(p, cnt);
double res = 0;
// for(int i = 0; i < qs.size(); i ++) cout << qs[i].num << ' '; cout << endl;
for(int i = 0; i < qs.size(); i ++) ans[qs[i].num] = 1;
}
else ans[p[0].num] = max_speed? 1 : 0;
for(int i = 0; i < n; i ++) if( vis[i] ) ans[i] = 0;
printf("Case #%d: ",cas++);
for(int i = 0; i < n; i ++) printf("%d",ans[i]);
printf("\n");
}
return 0;
}