模板：旋转卡壳（计算几何）_模版 旋转卡壳

所谓旋转卡壳，就是旋转起来的卡壳

（逃）

前言

前置知识：凸包
个人感觉很像 two-pointers 算法。
能够在优秀的线性时间复杂度内完成总多求最值（周长、面积…）的神奇操作。

解析

给出情境：

给出平面内的 $n$ 个点，求出所有点中的最远点对。
$n\le 10^5$

首先有一个结论：最远点对一定都是点集的凸包的顶点。
较为显然，证明可以考虑把凸包内的点延长到凸包一条边上，边两边的顶点一定有一个更优。

那么我们就转化成了求凸包上的最远点对，这个问题也叫做凸包的直径问题。

给出一些定义：

凸包的切线：若一条直线过凸包上的一点或一边，且整个凸包都在直线的同侧或在线上，那么我们就称这条直线为凸包的切线。
对踵点：如果经过凸包的两个顶点，可以作两条平行的凸包的切线，那么就称这两个点是一对对踵点。

不难发现，最远点对一定是一对对踵点。
然而个人感觉旋转卡壳这个知识点完全不需要这个概念。

考虑换一个角度，每次枚举边，然后用到边距离最远的点和边的两端点的距离来更新答案。（每次更新答案的点其实都是对踵点）
显然最优答案一定会被枚举到。
不难发现，如果我们逆时针枚举边，最远点的位置也是在逆时针旋转。
那么我们利用类似 two-pointers 的思想就可以线性的求出答案。
问题得以解决。

实现的细节上，我比较喜欢的方法是一开始先扫一遍暴力找到指针的起始位置，而不是倍长（野蛮）或者每次移动指针都更新答案（玄学）。

代码

P1452 [USACO03FALL]Beauty Contest G /【模板】旋转卡壳

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
inline ll read(){
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
  while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}

//basic declare
//#define double long double
const double eps=1e-10;
const double pi=acos(-1.0);

//---about vectors (or points)

//definition
struct V{
  double x,y;
  V():x(0),y(0){}
  V(double a,double b):x(a),y(b){}
};
V ans[10];//declared for other functions
int tot;
inline void input(V &a){scanf("%lf%lf",&a.x,&a.y);}
void print(const V &a,int op=1){printf("%.10lf %.10lf",a.x,a.y);putchar(op?10:32);}
//op:endl or space

//basic operation
inline V operator + (const V &a,const V &b){return (V){a.x+b.x,a.y+b.y};}
inline V operator - (const V &a,const V &b){return (V){a.x-b.x,a.y-b.y};}
inline V operator * (const double &x,const V &a){return (V){a.x*x,a.y*x};}
inline V operator * (const V &a,const double &x){return (V){a.x*x,a.y*x};}
inline V operator / (const V &a,const double x){return (V){a.x/x,a.y/x};}
inline bool operator == (const V &a,const V &b){return abs(a.x-b.x)<eps&&abs(a.y-b.y)<eps;}
inline bool operator != (const V &a,const V &b){return !(a==b);}
inline double operator * (const V &a,const V &b){return a.x*b.x+a.y*b.y;}
inline double operator ^ (const V &a,const V &b){return a.x*b.y-a.y*b.x;}
inline double len(const V &a){return sqrt(a.x*a.x+a.y*a.y);}
inline V mid(const V &a,const V &b){return (V){(a.x+b.x)/2,(a.y+b.y)/2};}
inline V chui(const V &a){return (V){a.y,-a.x};}//not take direction into account
inline V danwei(const V &a){return a/len(a);}
inline double tri_S(const V &a,const V &b,const V &c){return abs((b-a)^(c-a))/2;}//always be non-negative
inline bool operator < (const V &a,const V &b){
  	return a.x<b.x-eps||(abs(a.x-b.x)<eps&&a.y<b.y-eps);
}
inline double ang(const V &a,const V &b){return acos((a*b)/len(a)/len(b));}
inline V rotate(const V &o,double t){//COUNTER_CLOCKWISE
  	double s=sin(t),c=cos(t);
  	return (V){o.x*c-o.y*s,o.x*s+o.y*c};
}

const int N=1e5+100;
const int M=505;
int n,m;
V p[N],zhan[N];
bool cmp(V a,V b){
	double d=(a-p[1])^(b-p[1]);
	if(abs(d)>eps) return d>0;
	else return len(a-p[1])<len(b-p[1]);
}
void graham(V *p,int &n){
	int top=0;
	sort(p+1,p+1+n);
	sort(p+2,p+1+n,cmp);
	top=0;
	for(int i=1;i<=n;i++){
		while((top>1&&((zhan[top]-zhan[top-1])^(p[i]-zhan[top]))<=0)) --top;
		zhan[++top]=p[i];
	}
	memcpy(p,zhan,sizeof(zhan));
	n=top;
	return;
}
inline ll calc(const V &a,const V &b){
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+eps;
}
ll rotate_calipers(V *p,int n){
	ll res(0);
	int pl=1;
	for(int i=2;i<=n;i++){
		if(((p[2]-p[1])^(p[pl]-p[2]))<((p[2]-p[1])^(p[i]-p[2]))) pl=i;
	}
	for(int i=1;i<=n;i++){
		while(((p[i+1]-p[i])^(p[pl]-p[i+1]))<((p[i+1]-p[i])^(p[pl+1]-p[i+1]))){
			pl=(pl+1)%n;
			res=max(res,max(calc(p[i],p[pl]),calc(p[i+1],p[pl])));
		}
		res=max(res,max(calc(p[i],p[pl]),calc(p[i+1],p[pl])));
	}
	return res;
}
signed main(){
#ifndef ONLINE_JUDGE
  freopen("a.in","r",stdin);
  freopen("a.out","w",stdout);
#endif
	n=read();
	for(int i=1;i<=n;i++) input(p[i]);
	graham(p,n);
	p[0]=p[n];p[n+1]=p[1];
	//for(int i=1;i<=n;i++) print(p[i]);
	//putchar('\n');
	printf("%lld\n",rotate_calipers(p,n));
  	return 0;
}
/*
3 5
0 -2
-5 3
0 -7
*/




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
106
107
108
109
110
111
112
113
114
115
116
117
118
119