G25 旋转卡壳 • EH's Blog

题目情境#

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

题目描述

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

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

plaintext

输出 #1

plaintext

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

算法解析：#

旋转卡壳：先求凸包，再用双指针枚举凸包上的对踵点对：固定一个点，另一个沿凸包顺时针移动，用面积单调性判断卡壳位置，更新最大距离平方。 $O(n)$ ，用于求凸包直径、最远点对。

C++代码实现#

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define N 50010
#define x first
#define y second
#define Point pair<int,int>
Point p[N],s[N];
int n;

int cross(Point a,Point b,Point c){ //叉积
  return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int dis(Point a, Point b){ //距离平方
  return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
void Andrew(){
  sort(p+1,p+n+1);
  int t=0;
  for(int i=1; i<=n; i++){ //下凸包
    while(t>1&&cross(s[t-1],s[t],p[i])<=0)t--;
    s[++t]=p[i];
  }
  int k=t;
  for(int i=n-1; i>=1; i--){ //上凸包
    while(t>k&&cross(s[t-1],s[t],p[i])<=0)t--;
    s[++t]=p[i];
  }
  n=t-1; //n为凸包上的点数
}
int rotating_calipers(){ //旋转卡壳
  int res=0;
  for(int i=1,j=2; i<=n; i++){
    while(cross(s[i],s[i+1],s[j])<cross(s[i],s[i+1],s[j+1]))j=j%n+1;
    res=max(res,max(dis(s[i],s[j]),dis(s[i+1],s[j])));
  }
  return res;
}
int main(){
  scanf("%d",&n);
  for(int i=1; i<=n; i++) scanf("%d%d",&p[i].x,&p[i].y);
  Andrew();
  printf("%d\n",rotating_calipers());
  return 0;
}