Area of Mushroom
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2390 Accepted Submission(s): 578
Problem Description
Teacher Mai has a kingdom with the infinite area.
He has n students guarding the kingdom.
The i-th student stands at the position (xi,yi), and his walking speed is vi.
If a point can be reached by a student, and the time this student walking to this point is strictly less than other students, this point is in the charge of this student.
For every student, Teacher Mai wants to know if the area in the charge of him is infinite.
Input
There are multiple test cases, terminated by a line "0".
For each test case, the first line contains one integer n(1<=n<=500).
In following n lines, each line contains three integers xi,yi,vi(0<=|xi|,|yi|,vi<=10^4).
Output
For each case, output "Case #k: s", where k is the case number counting from 1, and s is a string consisting of n character. If the area in the charge of the i-th student isn't infinite, the i-th character is "0", else it's "1".
Sample Input
3
0 0 3
1 1 2
2 2 1
0
0 0 3
1 1 2
2 2 1
0
Sample Output
Case #1: 100
Author
xudyh
Source
简单凸包，但是！！调了好久！
首先凸包边上的点时可以算的，所以我算的两向量相乘等于0是可以加进去的，但是点有重复啊！所以两个点重复的时候会怎样？乘前面后面的都为0，即使后面的向量加进去之后是凹的。。所以必须判断下一个点是不是和前一个点重合，重合则删去，然后最后把有被重复的再删去。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<map>
#include<algorithm>
#define M(a,b) memset(a,b,sizeof(a))
using namespace std; int n; struct Node
{
long long x,y;
int num;
int flag;
int speed;
Node(int x=, int y=):x(x),y(y){}
bool operator < (const Node &rhs) const
{
if(x==rhs.x) return y<rhs.y;
return x<rhs.x;
}
}; int ans[]; long long cross(Node A, Node B) {return A.x*B.y-A.y*B.x;} typedef Node Vector;
Vector operator+(Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}
Vector operator-(Node A,Node B){return Vector(A.x-B.x,A.y-B.y);}
Vector operator*(Vector A,int p){return Vector(A.x*p,A.y*p);}
Vector operator/(Vector A,int p){return Vector(A.x/p,A.y/p);} int tubao(Node* poin,int cn,Node* che)
{
sort(poin,poin+cn);
int m = ;
for(int i = ;i<cn;i++)
{
while(m>&&(cross(che[m-]-che[m-],poin[i]-che[m-])<||(poin[i].x==che[m-].x&&poin[i].y==che[m-].y)))
{
//cout<<cross(che[m-1]-che[m-2],poin[i]-che[m-1])<<' '<<i<<'i'<<' '<<m<<'m'<<'!'<<endl;
m--;
}//cout<<cross(che[m-1]-che[m-2],poin[i]-che[m-1])<<' '<<i<<'i'<<' '<<m<<'m'<<endl;
che[m++] = poin[i];
//for(int i = 0;i<m;i++)
//cout<<che[i].x<<' '<<che[i].y<<endl;
//cout<<endl;
}
int k = m;
for(int i = cn-; i>= ;i--)
{
while(m>k&&(cross(che[m-]-che[m-],poin[i]-che[m-])<||(poin[i].x==che[m-].x&&poin[i].y==che[m-].y))) m--;
che[m++] = poin[i];
}
if(cn>) m--;
return m;
} int main()
{
int cas = ;
while(scanf("%d",&n)==&&n!=)
{
Node point[],point1[],ch[];
cas++;
M(ans,);
int a;
long long b,c;
int maxv = -;
for(int i = ;i<n;i++)
{
scanf("%I64d%I64d%d",&b,&c,&a);
point[i].x = b;
point[i].y = c;
point[i].num = i;
point[i].speed = a;
point[i].flag = ;
if(a>maxv) maxv = a;
}
int cnt = ;
for(int i = ;i<n;i++)
{
if(point[i].speed==maxv)
{
point1[cnt] = point[i];
cnt++;
}
}
sort(point1,point1+cnt);
for(int i = ;i<cnt-;i++)
{
if(point1[i].x==point1[i+].x&&point1[i].y==point1[i+].y)
point1[i].flag = ,point1[i+].flag = ;
}
int temm = tubao(point1,cnt,ch);
for(int i = ;i<temm;i++)
{
if(maxv==)
break;
//cout<<ch[i].x<<' '<<ch[i].y<<'!'<<endl;
if(ch[i].flag==)
ans[ch[i].num] = ;
}
printf("Case #%d: ",cas);
for(int i = ;i<n;i++)
{
printf("%d",ans[i]);
}
printf("\n");
}
return ;
}