poj2187 Beauty Contest

题意

平面上有$n$个点,求出最远点对距离的平方($n\leq 50000$)。

Graham

平面上这个点集的最远点对一定是凸包上的两点,那么首先要求出凸包。

将凸包分为上凸包和下凸包,维护一个栈,加入新的点的时候,设栈最后两个点是$i,j$,新加入的点为$k$,当出现以下情况时需要弹出栈尾$j$以维持现有点集的凸性:

a

在上述情况下,$\overrightarrow{jk}$在$\overrightarrow{ij}$的左手系,即$\overrightarrow{jk} \times \overrightarrow{ij} <0$(若满足下凸壳的性质,$jk$会在$ij$的右手系)。

于是将点集按字典序排序,向右找一遍上凸壳,向左找一遍下凸壳即可得到凸包。复杂度带排序是$O(nlogn)$。

得到凸包以后,需要求最远距离的点对,会达到$O(m^2)$(m为凸包点数)。然而朴素的求法对于凸包上的一个点实质上枚举了很多不必要的点,考虑只枚举有用的点。

旋转卡壳

延与凸包某条边的法线垂直的方向卡住凸包的两条平行线之间的距离即为凸包上某个点到对面最远点的距离,更新即可。

具体的做法是先得到凸包的左右最远点,然后移动其中一个点使得平行线旋转。旋转时要判断移动哪个点能使得不转多了角度漏下点,例如下图从虚线转到实线是$I\rightarrow {I+1}$的变化。判断方法是,(设$I$到$I+1$的向量为$\overrightarrow{i}$,$\overrightarrow j$同理),若$\overrightarrow{i}$在$\overrightarrow{j}$的左手系则移动$I$点(见图),在右手系则移动$J$点。)

b

复杂度$O(n)$。总的复杂度$O(nlogn)$。

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
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps=1e-10;
const int maxn=50000+5;
double add(double x,double y)
{
if(abs(x+y)<eps*(abs(x)+abs(y))) return 0;
else return x+y;
}
struct P{
double x,y;
P(double x=0,double y=0): x(x),y(y) {}
double len() {return add(x*x,y*y);}
P operator+(P oth) {return P(x+oth.x,y+oth.y);}
P operator-(P oth) {return P(x-oth.x,y-oth.y);}
P operator*(double k) {return P(x*k,y*k);}
double dot(P oth) {return add(x*oth.x,y*oth.y);}
double det(P oth) {return add(x*oth.y,-y*oth.x);}
};
P pts[maxn],hl[maxn];
bool cmp(P a,P b) {
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
int n,k;
void grh()
{
k=0;
for(int i=1;i<=n;i++) {
while(k>=2 && (hl[k]-hl[k-1]).det(pts[i]-hl[k])<=0.0) k--;
hl[++k]=pts[i];
}
int up=k;
for(int i=n-1;i>=1;i--) {
while(k>up && (hl[k]-hl[k-1]).det(pts[i]-hl[k])<=0.0) k--;
hl[++k]=pts[i];
}
--k;
}
int getmod(int id,int mo)
{
if(id%mo==0) return mo;
else return id%mo;
}
double rot()
{
if(k==2) return (hl[2]-hl[1]).len();
int si=1,sj=1;
double ans=-1.0;
for(int i=1;i<=k;i++) {
if(cmp(hl[i],hl[si])) si=i;
if(cmp(hl[sj],hl[i])) sj=i;
}
int i=si,j=sj;
while(i!=sj || j!=si) {
ans=max(ans,(hl[i]-hl[j]).len());
if((hl[getmod(i+1,k)]-hl[i]).det(hl[getmod(j+1,k)]-hl[j])<0) i=getmod(i+1,k);
else j=getmod(j+1,k);
}
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf%lf",&pts[i].x,&pts[i].y);
sort(pts+1,pts+1+n,cmp);
grh();
printf("%.0f\n",rot());
return 0;
}