【poor 几何】UVA1606 转啊转啊转

Posted by Cww97 on 2016-02-23

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/50720204
题目

可怕,可怕
atan2教做人,之前根本不知道有这个函数
看了刘汝佳的代码,又看了这篇题解,这孩子在评论区放的图很亮
向量差积教做人,这个性质早忘了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1100;
struct point{
int x,y,col;double rad;
point(int x=0,int y=0):x(x),y(y){}
bool operator < (const point &a)const
{return rad<a.rad;}
bool operator ^ (const point &a)const
{return x*a.y-y*a.x>=0;}
point operator - (const point &a)const
{return point(x-a.x,y-a.y);}
}a[N],p[N],zero;
int n,L,R,cnt;
int main(){
freopen("fuck.in","r",stdin);
zero.x=zero.y=0;
for (;~scanf("%d",&n)&&n;){
for (int i=0;i<n;i++)
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].col);
int ans=0;
for (int i=0;i<n;i++){
int P=0;

for (int j=0;j<n;j++){
if (i==j)continue;
p[P]=a[j]-a[i];
if (a[j].col)p[P]=zero-p[P];
p[P].rad=atan2(p[P].y,p[P].x);
P++;
}
sort(p,p+P);
for (int j=0;j<P;j++)
//printf("x=%d y=%d rad=%.2lf\n",p[j].x,p[j].y,p[j].rad);
L=0;R=0;cnt=2;
for (;L<P;){
if (L==R){R=(R+1)%P;cnt++;}
while(L!=R&&p[L]^p[R]){R=(R+1)%P;cnt++;}
L++; cnt--; ans=max(ans,cnt);
//printf("L=%d R=%d ans=%d\n",L-1,R,ans);
}
//printf("base=%d ans=%d\n",i,ans);
}
printf("%d\n",ans);
}
return 0;
}