旋转卡壳
写在题解之前，
2020.6.11更新：纠正了错误代码
2021.3.12更新：你谷新数据把我卡死了，为避免误人子弟，纠正了错误代码。原本的错误：没有考虑在同一直线的情况，而且在旋转卡壳求直径时，取对踵点的编号有误
原本的错误2：凸包就是个三角形，导致取对踵点有误，建议加上邻边取max
比如：
输入：
4
-1000 -1000
-2000 0
-90 -90
0 0
应当求出的凸包队列：-1000 -1000, 0 0, -2000 0
但可能得出的：-1000 -1000，-90 -90，-2000 0
附上可以hack起码两篇题解的数据：
3
-1 18
1 6
3 -6
应当得到的答案：592
但是好几位巨佬输出了148
这三点都在同一直线上，属于特殊情况
但显然题目中n个点是随机给出的，没有限制
若刻意构造可以卡掉很多做法
对于构造凸包时三点在同一直线时，应取较长的线段。求二维凸包的直径，
先放巨佬博客：
- 旋转卡壳算法
- 旋转卡壳法总结
讲的都炒鸡好
我们将一个多边形上任意两点间的距离的最大值定义为多边形的直径。 显然直接枚举太慢了。那么有一个O(n)的算法：旋转卡壳,计算时就像一对平行卡壳卡住凸包旋转而得名。
先上图（转载），很形象的展示了旋转卡壳的过程
显然直径是由多边形的平行切线的最远距离决定的， 所以我们只需要查询对踵点对，找到距离最远的那一对(定义如果过凸包上的两个点可以画一对平行直线，使凸包上的所有点都夹在两条平行线之间或落在平行线上，那么这两个点叫做一对对踵点)。
在卡壳旋转的过程中，会出现夹住点点、边边、点边的情况，但是显然，我们只需要枚举点边的情况，就可以找到所有的对踵点对。
一个对踵点到对应边之间的距离比其他点要大。而且在边确定时，这个距离是可以转化为三角形面积的(小学数学)
前提：已经得到了二维凸包顶点的顺序序列。
首先确定第一条边，显然这个时候组成的三角形面积关于点的函数是一个单峰函数，那么可以枚举出它的对应点。
在这之后，只需要继续扩展边，一步步往后走，而对于对应点而言，如果更新，显然也是逆时针往后，这时根据单峰函数的性质，只需判断下一步是否会使构成的三角形面积变小即可。
O(n)遍历凸包，中途记录对应点到边的两顶点的最大距离，遍历完后显然就得到了答案。
上——代码
#include <bits/stdc++.h>
using namespace std;
int n;
struct node{
double x,y;
}p[100005],s[100005];
double d(node p1,node p2)//两点间距离
{
double ans=(p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x);
if(ans>0){
return ans;
}else{
return ans*(-1);
}
}
double check1(node a1,node a2,node b1,node b2)//检查叉积是否大于0，如果是a就逆时针转到b
//因为ACxAB和ABxAC的正负值是不同的
{
return (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y);
}
double check2(node a1,node a2,node b1,node b2)//用于在构造凸包时进行判断，如果在同一直线上，就返回两线段长度的差，显然如果s[tot]此时较短，那么它就会被弹出，由p[i]取而代之
{
double ans= (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y);
if(ans==0){
return d(a1,a2)-d(b1,b2);
}
return ans;
}
bool cmp(node p1,node p2)//排序函数，按照极角排序
{
double tmp=check1(p[1],p1,p[1],p2);
if(tmp>0) //p1转到p2所以p1在前
return 1;
if(tmp==0&&d(p[0],p1)<d(p[0],p2)) //虽然角度相同但是p1距离更远，也是p1在前
return 1;
return 0;
}
double mianji(node a,node b,node c){//求三点组成的三角形的面积 蒟蒻只会用割补法
double xi=min(a.x,min(b.x,c.x));
double yi=min(a.y,min(b.y,c.y));
double xa=max(a.x,max(b.x,c.x));
double ya=max(a.y,max(b.y,c.y));
double ansi=(xa-xi)*(ya-yi);
ansi-=(max(a.x,b.x)-min(a.x,b.x))*(max(a.y,b.y)-min(a.y,b.y))/2;
ansi-=(max(a.x,c.x)-min(a.x,c.x))*(max(a.y,c.y)-min(a.y,c.y))/2;
ansi-=(max(c.x,b.x)-min(c.x,b.x))*(max(c.y,b.y)-min(c.y,b.y))/2;
return ansi;
}
int tot=1;
int main(){
scanf("%d",&n);
double tmp;
for(int i=1;i<=n;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);
if(i!=1)//记录最低最右的点
{
if(p[i].y<p[1].y||(p[i].y==p[1].y)&&p[i].x<p[1].x){
tmp=p[1].y;p[1].y=p[i].y;p[i].y=tmp;
tmp=p[1].x;p[1].x=p[i].x;p[i].x=tmp;
}
}
}
sort(p+2,p+1+n,cmp);
s[1]=p[1];
for(int i=2;i<=n;i++){
while(tot!=1&&(check2(s[tot-1],s[tot],s[tot],p[i])<=0)){
tot--;
}
tot++;
s[tot]=p[i];
}
s[tot+1]=p[1];//最后要封闭图形
// for(int i=1;i<=tot;i++){
// cout<<s[i].x<<" "<<s[i].y<<endl;
// }
if(tot==2){//假如只有两个点
cout<<(long long)(d(s[1],s[2]))<<endl;
return 0;
}
double ans=0;
int num=3;//先确定的边是 1 2 ，那么对应点从3开始枚举
for(int i=1;i<=tot;i++){//枚举边
ans=max(ans,d(s[i],s[i+1]));//邻边取max，可以过你谷更新的三角形取邻边情况
while(mianji(s[i],s[i+1],s[num])<mianji(s[i],s[i+1],s[num+1])){//假如对应点能继续走
num++;
if(num==tot+1){//这是之前错误的地方之一,我的程序记录的编号是从1-tot,tot+1就是1号点
num=1;//所以假如对踵点等于tot+1，就要使其等于一，便于下次自增
}
}
// cout<<i<<" "<<i+1<<" "<<num<<endl;
ans=max(ans,max(d(s[i],s[num]),d(s[i+1],s[num])));
}
cout<<(long long)(ans)<<endl;
return 0;
}