-
Notifications
You must be signed in to change notification settings - Fork 0
/
2187.cpp
50 lines (48 loc) · 1.31 KB
/
2187.cpp
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 <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define fromto(from,to,i) for(int i=(from);i<=(to);++i)
#define MAXN 50008
typedef pair<double,double> Point;
double cross(Point x,Point y) {
return x.first*y.second-x.second*y.first;
}
Point operator-(Point x,Point y) {
return Point(x.first-y.first,x.second-y.second);
}
double area2(Point x,Point y,Point z) {
return fabs(cross(x-y,z-y));
}
double len2(Point x) {
return x.first*x.first+x.second*x.second;
}
Point P[MAXN],TB[MAXN];
int main()
{
int n;
scanf("%d",&n);
fromto(1,n,i) scanf("%lf%lf",&(P[i].first),&(P[i].second));
sort(P+1,P+n+1);
n=unique(P+1,P+n+1)-P-1;
int k=0;
for(int i=1;i<=n;++i) {
for(;k>=2 && cross(TB[k]-TB[k-1],P[i]-TB[k])<=0;--k);
TB[++k]=P[i];
}
for(int i=n-1,t=k;i>=1;--i) {
for(;k>=t+1 && cross(TB[k]-TB[k-1],P[i]-TB[k])<=0;--k);
TB[++k]=P[i];
}
--k;
//凸包免费赠送TB[k+1]这个哨兵哦~~
//fromto(1,k,i) printf("(%lf,%lf)\n",TB[i].first,TB[i].second);
double ans=0.0;
for(int i=1,j=2;i<=k;++i) {
while(area2(TB[i],TB[i+1],TB[j+1])>area2(TB[i],TB[i+1],TB[j])) j=j%k+1;
ans=max(ans,max(len2(TB[j]-TB[i]),len2(TB[j+1]-TB[i+1])));
}
printf("%.0lf\n",ans);
return 0;
}