1. Luogu P1452 [USACO03FALL]Beauty Contest G /【模板】旋转卡壳
思路：距离最远的点一定是凸壳上的两点
双指针枚举，i指针枚举凸壳的边，j指针在前面枚举最远点，优选答案
注意，两个指针都是向前走的，保证旋转卡壳时间为O(n)
时间：O(n*logn + n)
1 #include <iostream>
2 #include <cstring>
3 #include <algorithm>
4 using namespace std;
5
6 #define N 50010
7 #define x first
8 #define y second
9 #define Point pair<int,int>
10 Point p[N],s[N];
11 int n;
12
13 int cross(Point a,Point b,Point c){ //叉积
14 return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
15 }
16 int dis(Point a, Point b){ //距离平方
17 return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
18 }
19 void Andrew(){
20 sort(p+1,p+n+1);
21 int t=0;
22 for(int i=1; i<=n; i++){ //下凸包
23 while(t>1&&cross(s[t-1],s[t],p[i])<=0)t--;
24 s[++t]=p[i];
25 }
26 int k=t;
27 for(int i=n-1; i>=1; i--){ //上凸包
28 while(t>k&&cross(s[t-1],s[t],p[i])<=0)t--;
29 s[++t]=p[i];
30 }
31 n=t-1; //n为凸包上的点数
32 }
33 int rotating_calipers(){ //旋转卡壳
34 int res=0;
35 for(int i=1,j=2; i<=n; i++){
36 while(cross(s[i],s[i+1],s[j])<cross(s[i],s[i+1],s[j+1]))j=j%n+1;
37 res=max(res,max(dis(s[i],s[j]),dis(s[i+1],s[j])));
38 }
39 return res;
40 }
41 int main(){
42 scanf("%d",&n);
43 for(int i=1; i<=n; i++) scanf("%d%d",&p[i].x,&p[i].y);
44 Andrew();
45 printf("%d\n",rotating_calipers());
46 return 0;
47 }
2. Luogu P4166 [SCOI2007]最大土地面积
思路：内接四边形的对角线一定是凸包的对角线
枚举凸包的对角线，旋转卡壳求最远点a,b，更新答案
时间：O(n*logn + n*n)
1 #include<cstring>
2 #include<iostream>
3 #include<algorithm>
4 #include<cmath>
5 using namespace std;
6
7 const double eps=1e-8;
8 const double PI=acos(-1);
9 #define N 50010
10 #define x first
11 #define y second
12 #define Point pair<int,int>
13 Point p[N],s[N];
14 int n;
15
16 Point operator+(Point a, Point b){ //向量+
17 return {a.x+b.x, a.y+b.y};
18 }
19 Point operator-(Point a, Point b){ //向量-
20 return {a.x-b.x, a.y-b.y};
21 }
22 Point operator*(Point a, double p){ //数乘
23 return {a.x*p, a.y*p};
24 }
25 double cross(Point a,Point b,Point c){ //叉积
26 return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
27 }
28 double dot(Point a,Point b,Point c){ //点积
29 return (b.x-a.x)*(c.x-a.x)+(b.y-a.y)*(c.y-a.y);
30 }
31 double dis(Point a,Point b){ //距离
32 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
33 }
34 Point rotate(Point a, double b){ //逆转角
35 return {a.x*cos(b)-a.y*sin(b), a.x*sin(b)+a.y*cos(b)};
36 }
37 bool cmp(Point a, Point b){ //找最低点
38 return fabs(a.y-b.y)>eps ? a.y<b.y : a.x<b.x;
39 }
40 void zero(Point &a){ //避免-0.00000
41 if(fabs(a.x)<=eps) a.x=0;
42 if(fabs(a.y)<=eps) a.y=0;
43 }
44 void Andrew(){
45 sort(p+1,p+n+1);
46 int t=0;
47 for(int i=1; i<=n; i++){ //下凸包
48 while(t>1 && cross(s[t-1],s[t],p[i])<=0)t--;
49 s[++t]=p[i];
50 }
51 for(int k=t, i=n-1; i>=1; i--){ //上凸包
52 while(t>k && cross(s[t-1],s[t],p[i])<=0)t--;
53 s[++t]=p[i];
54 }
55 n=t-1; //n为凸包上的点数
56 }
57 void rotating_calipers(){ //旋转卡壳
58 double ans=1e20;
59 int a,b,c; a=b=2; //上a,右b,左c
60 for(int i=1;i<=n;i++){
61 while(cross(s[i],s[i+1],s[a])<cross(s[i],s[i+1],s[a+1]))a=a%n+1;
62 while(dot(s[i],s[i+1],s[b])<dot(s[i],s[i+1],s[b+1]))b=b%n+1;
63 if(i==1)c=a;
64 while(dot(s[i+1],s[i],s[c])<dot(s[i+1],s[i],s[c+1]))c=c%n+1;
65 double d=dis(s[i],s[i+1]);
66 double H=cross(s[i],s[i+1],s[a])/d;
67 double R=dot(s[i],s[i+1],s[b])/d;
68 double L=dot(s[i+1],s[i],s[c])/d;
69 if(ans>(R+L-d)*H){
70 ans=(R+L-d)*H;
71 p[1]=s[i+1]+(s[i]-s[i+1])*(L/d);
72 p[2]=s[i]+(s[i+1]-s[i])*(R/d);
73 p[3]=p[2]+rotate(s[i+1]-s[i],PI/2)*(H/d);
74 p[4]=p[1]+rotate(s[i+1]-s[i],PI/2)*(H/d);
75 }
76 }
77 printf("%.5lf\n",ans);
78 int k=1;
79 for(int i=2;i<=4;i++) if(cmp(p[i],p[k]))k=i; //找最低点
80 for(int i=1; i<=4; i++){
81 zero(p[k]);
82 printf("%.5lf %.5lf\n",p[k].x,p[k].y);
83 k=k%4+1;
84 }
85 }
86 int main(){
87 scanf("%d",&n);
88 for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
89 Andrew();
90 rotating_calipers();
91 return 0;
92 }
3. Luogu P3187 [HNOI2007]最小矩形覆盖
思路：最小矩形的某条边一定在凸壳上的某条边上
枚举凸壳的边，旋转卡壳求三点
时间：O(n*logn + n)
1 #include<cstring>
2 #include<iostream>
3 #include<algorithm>
4 #include<cmath>
5 using namespace std;
6
7 const double eps=1e-8;
8 const double PI=acos(-1);
9 #define N 50010
10 #define x first
11 #define y second
12 #define Point pair<int,int>
13 Point p[N],s[N];
14 int n;
15
16 Point operator+(Point a, Point b){ //向量+
17 return {a.x+b.x, a.y+b.y};
18 }
19 Point operator-(Point a, Point b){ //向量-
20 return {a.x-b.x, a.y-b.y};
21 }
22 Point operator*(Point a, double p){ //数乘
23 return {a.x*p, a.y*p};
24 }
25 double cross(Point a,Point b,Point c){ //叉积
26 return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
27 }
28 double dot(Point a,Point b,Point c){ //点积
29 return (b.x-a.x)*(c.x-a.x)+(b.y-a.y)*(c.y-a.y);
30 }
31 double dis(Point a,Point b){ //距离
32 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
33 }
34 Point rotate(Point a, double b){ //逆转角
35 return {a.x*cos(b)-a.y*sin(b), a.x*sin(b)+a.y*cos(b)};
36 }
37 bool cmp(Point a, Point b){ //找最低点
38 return fabs(a.y-b.y)>eps ? a.y<b.y : a.x<b.x;
39 }
40 void zero(Point &a){ //避免-0.00000
41 if(fabs(a.x)<=eps) a.x=0;
42 if(fabs(a.y)<=eps) a.y=0;
43 }
44 void Andrew(){
45 sort(p+1,p+n+1);
46 int t=0;
47 for(int i=1; i<=n; i++){ //下凸包
48 while(t>1 && cross(s[t-1],s[t],p[i])<=0)t--;
49 s[++t]=p[i];
50 }
51 for(int k=t, i=n-1; i>=1; i--){ //上凸包
52 while(t>k && cross(s[t-1],s[t],p[i])<=0)t--;
53 s[++t]=p[i];
54 }
55 n=t-1; //n为凸包上的点数
56 }
57 void rotating_calipers(){ //旋转卡壳
58 double ans=1e20;
59 int a,b,c; a=b=2; //上a,右b,左c
60 for(int i=1;i<=n;i++){
61 while(cross(s[i],s[i+1],s[a])<cross(s[i],s[i+1],s[a+1]))a=a%n+1;
62 while(dot(s[i],s[i+1],s[b])<dot(s[i],s[i+1],s[b+1]))b=b%n+1;
63 if(i==1)c=a;
64 while(dot(s[i+1],s[i],s[c])<dot(s[i+1],s[i],s[c+1]))c=c%n+1;
65 double d=dis(s[i],s[i+1]);
66 double H=cross(s[i],s[i+1],s[a])/d;
67 double R=dot(s[i],s[i+1],s[b])/d;
68 double L=dot(s[i+1],s[i],s[c])/d;
69 if(ans>(R+L-d)*H){
70 ans=(R+L-d)*H;
71 p[1]=s[i+1]+(s[i]-s[i+1])*(L/d);
72 p[2]=s[i]+(s[i+1]-s[i])*(R/d);
73 p[3]=p[2]+rotate(s[i+1]-s[i],PI/2)*(H/d);
74 p[4]=p[1]+rotate(s[i+1]-s[i],PI/2)*(H/d);
75 }
76 }
77 printf("%.5lf\n",ans);
78 int k=1;
79 for(int i=2;i<=4;i++) if(cmp(p[i],p[k]))k=i; //找最低点
80 for(int i=1; i<=4; i++){
81 zero(p[k]);
82 printf("%.5lf %.5lf\n",p[k].x,p[k].y);
83 k=k%4+1;
84 }
85 }
86 int main(){
87 scanf("%d",&n);
88 for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
89 Andrew();
90 rotating_calipers();
91 return 0;
92 }
练习题
1 #include <iostream>
2 #include <cstring>
3 #include <algorithm>
4 using namespace std;
5
6 #define N 50010
7 #define x first
8 #define y second
9 #define Point pair<int,int>
10 Point p[N],s[N];
11 int n,top;
12
13 int cross(Point a,Point b,Point c){ //叉积
14 return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
15 }
16 void Andrew(){
17 sort(p+1,p+n+1);
18 top=0;
19 for(int i=1; i<=n; i++){ //下凸包
20 while(top>1&&cross(s[top-1],s[top],p[i])<=0)top--;
21 s[++top]=p[i];
22 }
23 int t=top;
24 for(int i=n-1; i>=1; i--){ //上凸包
25 while(top>t&&cross(s[top-1],s[top],p[i])<=0)top--;
26 s[++top]=p[i];
27 }
28 n=top-1; //n为凸包上的点数
29 }
30 int rotating_calipers(){ //旋转卡壳
31 int res=0;
32 for(int i=1; i<=n; i++){
33 int k=i+1; //k为j到i之间的点
34 for(int j=i+1; j<=n; j++){
35 while(cross(s[i],s[j],s[k+1])>cross(s[i],s[j],s[k]))k=k%n+1;
36 res=max(res,cross(s[i],s[j],s[k]));
37 }
38 }
39 return res;
40 }
41 int main(){
42 while(scanf("%d",&n),n!=-1){
43 for(int i=1; i<=n; i++) scanf("%d%d",&p[i].x,&p[i].y);
44 Andrew();
45 printf("%.2f\n",rotating_calipers()/2.);
46 }
47 return 0;
48 }
标签：return,Point,int,cross,旋转,卡壳,include,define From： https://www.cnblogs.com/rw666/p/17996855