旋转卡壳

Smiling-Weeping / 2023-08-19 / 原文

Smiling & Weeping

　　　　　　　　　　　　　　　　---- 一个能升起月亮的身体，必然驮住了无数次日落

题目链接：https://www.luogu.com.cn/problem/P1452

题目简介：

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

## 题目描述

给定平面上 $n$ 个点，求凸包直径。

## 输入格式

第一行一个正整数 $n$。
接下来 $n$ 行，每行两个整数 $x,y$，表示一个点的坐标。

## 输出格式

输出一行一个整数，表示答案的平方。

## 样例 #1

### 样例输入 #1

```
4
0 0
0 1
1 1
1 0
```

### 样例输出 #1

```
2
```

## 提示

【数据范围】
对于 $100\%$ 的数据，$2\le n \le 50000$，$|x|,|y| \le 10^4$。

Talk is cheap , show me the code

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1e5+1;
 4 const double eps=1e-6;
 5 int n;
 6 int sgn(double x){
 7     if(fabs(x)<eps) return 0;
 8     else
 9         return x<0 ? -1 : 1;
10 }
11 struct Point{
12     double x , y;
13     Point() {}
14     Point(double x , double y) : x(x),y(y) {}
15     Point operator + (Point b) {return Point(x+b.x , y+b.y); }
16     Point operator - (Point b) {return Point(x-b.x , y-b.y); }
17     bool operator == (Point b) {return sgn(x-b.x)==0 && sgn(y-b.y)==0; }
18     bool operator < (const Point& b){
19         return sgn(x-b.x)<0 || (sgn(x-b.x)==0 && sgn(y-b.y)<0);
20     }
21 };
22 typedef Point Vector;
23 double Cross(Vector a , Vector b){
24     return a.x*b.y-a.y*b.x;
25 }
26 vector<Point> v;        // 存所有点，并进行从小到大排序
27 double line[N],ptr=0;   // 保存半个凸壳的路径
28 vector<Point> hull;     // 保存完整凸壳的路径
29 Point p[N],ch[N];
30 int convex() // 求凸壳
31 {
32     sort(p,p+n);
33     n = unique(p,p+n)-p;
34     int u=0;
35     for(int i = 0; i < n; i++){
36         while(u>1 && sgn(Cross(ch[u-1]-ch[u-2] , p[i]-ch[u-1]))<=0)
37             u--;
38         ch[u++]=p[i];
39     }
40     int j = u;
41     for(int i = n-2; i >= 0; i--){
42         while(u>j && sgn(Cross(ch[u-1]-ch[u-2],p[i]-ch[u-1]))<=0)
43             u--;
44         ch[u++]=p[i];
45     }
46     if(n>1) u--;
47     return u;
48 }
49 double Distance(Point& a , Point& b){
50     return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
51 }
52 double rotateCalipers(int len){
53     double ans = -1;
54     int size = len;
55     int op = 1; // 对面的点，逆时针沿凸包移动
56     Point p1,p2;
57     for(int i = 0; i < size; i++){
58         p1 = ch[i]; p2 = ch[(i+1)%size];
59         while(Cross(p2-ch[(op+1)%size],p1-ch[(op+1)%size]) < Cross(p2-ch[op] , p1-ch[op]))
60             op = (op+1)%size;
61         ans = max(ans , max(Distance(p1 , ch[op]) , Distance(p2 , ch[op])));
62     }
63     return ans;
64 }
65 int main()
66 {
67     double x,y;
68     scanf("%d",&n);
69     for(int i = 0; i < n; i++){
70         scanf("%lf %lf",&x,&y);
71         p[i] = Point(x,y);
72     }
73     int len = convex();
74     printf("%d\n",(int)rotateCalipers(len));
75     return 0;
76 }