poj2187 Beauty Contest

Link

Solution

旋转卡壳 # Tips 旋转卡壳 刚开始要用第二个点卡第一条边 # Code

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
//Code by Lucida
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define red(x) scanf("%d",&x)
#define fred(x) scanf("%lf",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
using std::sort;
using std::swap;
using std::unique;
const int MAXN=50000+1;
typedef double ld;
const ld eps=1e-7;
int fcmp(ld x)
{
if(-eps<x && x<eps) return 0;
return x<0?-1:1;
}
template <class T> T sqr(T a){return a*a;}
template <class T> T abs(T a){return a>0?a:-a;}
struct vec
{
ld x,y;
vec(ld _x=0,ld _y=0):x(_x),y(_y){}
bool operator <(const vec &a) const
{
if(x!=a.x) return x<a.x;
return y<a.y;
}
void operator +=(vec a){x+=a.x,y+=a.y;}
void operator -=(vec a){x-=a.x,y-=a.y;}
bool operator ==(const vec &a) const{return x==a.x && y==a.y;}
ld norm(){return sqrt(x*x+y*y);}
};
typedef vec point;
vec operator +(vec a,vec b){return vec(a.x+b.x,a.y+b.y);}
vec operator -(vec a,vec b){return vec(a.x-b.x,a.y-b.y);}
vec operator *(vec a,ld t){return vec(a.x*t,a.y*t);}
vec operator /(vec a,ld t){return vec(a.x/t,a.y/t);}
ld inner(vec a,vec b){return a.x*b.x+a.y*b.y;}
ld outer(vec a,vec b){return a.x*b.y-a.y*b.x;}
struct line
{
point a;vec v;
line(point _a,vec _v):a(_a),v(_v){}
};
bool cmp(vec a,vec b)
{
if(fcmp(outer(a,b))!=0)
return fcmp(outer(a,b))>0;
return inner(a,a)<inner(b,b);
}
void Graham(point *p,int n,point *stack,int &top)
{
top=0;
int mi=1;
for(int i=1;i<=n;i++) if(p[i]<p[mi]) mi=i;
swap(p[1],p[mi]),p[0]=p[1];
for(int i=1;i<=n;i++) p[i]-=p[0];
sort(p+2,p+1+n,cmp);
n=unique(p+1,p+1+n)-p-1;
p[n+1]=p[1];
for(int i=1;i<=n+1;i++) p[i]+=p[0];
for(int i=1;i<=n+1;i++)
{
while(top>=2 && fcmp(outer(p[i]-stack[top],stack[top]-stack[top-1]))>=0) top--;
stack[++top]=p[i];
}
top--;
}
ld dist(point a,point b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
ld dist(point a,line l){return abs(outer(a-l.a,l.v))/l.v.norm();}
ld dist2(point a,point b){return sqr(a.x-b.x)+sqr(a.y-b.y);}
int main()
{
freopen("input","r",stdin);
static point p[MAXN],hull[MAXN];
int n,nb;red(n);
for(int i=1;i<=n;i++) fred(p[i].x),fred(p[i].y);
Graham(p,nb=n,hull,n);
ld ANS=0;
if(n==1)
{
n=nb;
sort(p+1,p+1+n);
ANS=dist2(p[1],p[n]);
}
else
{
#define suc(i) (i+1>n?1:i+1)
for(int i=1,cur=2;i<=n;i++)
{
line now(hull[i],hull[suc(i)]-hull[i]);
while(fcmp(dist(hull[cur],now)-dist(hull[suc(cur)],now))<0)
cur=suc(cur);
chkmx(ANS,dist2(hull[i],hull[cur]));
chkmx(ANS,dist2(hull[suc(i)],hull[cur]));
}
#undef suc
}
printf("%.0f\n",ANS);
return 0;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利