计算机几何，极角序，旋转卡壳的板子

最近春招笔试遇到的很眼熟的算法，复习一下~

https://ac.nowcoder.com/acm/contest/66585/D

https://ac.nowcoder.com/acm/contest/66585/E

https://ac.nowcoder.com/acm/contest/66585/G

#include<bits/stdc++.h>
using namespace std;
const int N=2200;
typedef long long db; //全整形直接在这里改 
typedef long long ll;
const db EPS=0;
inline int sign(db a){return a<-EPS?-1:a>EPS;}  //判断a的符号
inline int cmp(db a,db b){return sign(a-b);}
struct P{
	db x,y;
	P(){}
	P(db _x,db _y):x(_x),y(_y){}
	P operator+(P p){return{x+p.x,y+p.y};}
	P operator-(P p){return{x-p.x,y-p.y};}
	P operator*(db d){return{x*d,y*d};}
	P operator/(db d){return{x/d,y/d};}
	
	bool operator<(P p) const{
		int c=cmp(x,p.x);
		if(c) return c==-1;
		return cmp(y,p.y)==-1;
    }
	
	bool operator==(P o) const{
		return cmp(x,o.x)==0&&cmp(y,o.y)==0;
	}
	
	db dot(P p) {return x*p.x+y*p.y;} 
	//对应相乘的点积 |a|*|b|*cosC
	db det(P p) {return x*p.y-y*p.x;}  
	//交差相乘再相减的叉积 |a|*|b|*sinC,有方向以第一个向量为准 ==平行四边形的面积 
	db distTo(P p){return (*this-p).abs();} //|x1-x2|+|y1-y2|
	db alpha(){return atan2(y,x);}  //极角与x轴正半轴的夹角 弧度制 
	db abs(){return sqrt(abs2());}
	db abs2(){ return x*x+y*y;}  //到原点的距离平方 
	P rot90(){return P(-y,x);}  //旋转90 
	P unit(){return *this/abs();} //除于模长
	int quad() const{return sign(y)==1||(sign(y)==0&&sign(x)>=0);} //判断是不是位于上半
};
#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y)) 
//算(^^p1p2)X(^^p1p3) 
#define crossOp(p1,p2,p3) sign(cross(p1,p2,p3))
// crossOp 精度有一点问题 点的范围1e9 eps<=10^(-9) 
//算一个上面的符号 
bool chkLL(P p1, P p2, P q1,P q2){
	db a1=cross(q1,q2,p1),a2=-cross(q1,q2,p2);
	return sign(a1+a2)!=0;
}
// 两条直线是不是相交关系
// p1p2,q1q2 是不是恰有一个交点
P isLL(P p1,P p2,P q1,P q2){
	db a1=cross(q1,q2,p1),a2=-cross(q1,q2,p2);
	return (p1*a2+p2*a1)/(a1*a2);
} 
//通过叉积求出面积，然后等比分线段，求p1,p2的交点 
bool intersect(db l1,db r1,db l2,db r2){
	if(l1>r1) swap(l1,r1);if(l2>r2) swap(l2,r2);
	return !( cmp(r1,l2)==-1 || cmp(r2,l1)==-1 );
}
// 判断l1,l2 是否相交 ，可以重，一个点 
bool isSS(P p1,P p2,P q1,P q2){
	return intersect(p1.x,p2.x,q1.x,q2.x)&&intersect(p1.y,p2.y,q1.y,q2.y)&&
	crossOp(p1,p2,q1)*crossOp(p1,p2,q2)<=0&&crossOp(q1,q2,p1)*
	crossOp(q1,q2,p2)<0;
}
//判断是不是严格相交有且仅有一个交点 
bool isSS_strict(P p1, P p2, P q1, P q2){
	return crossOp(p1,p2,q1)*crossOp(p1,p2,q2)<0&&crossOp(q1,q2,p1)*
	crossOp(q1,q2,p2)<0;
}
bool isMiddle(db a,db m,db b){
/*	
	if(a>b) swap(a,b);
	return cmp(a,m)<=0&&cmp(m,b)<=0;
*/
	return sign(a-m)==0|| sign(b-m)==0|| (a<m!=b<m);
}
// 判断一个点是否在两个点之间 
bool isMiddle(P a,P m,P b){
	return isMiddle(a.x,m.x,b.x) && isMiddle(a.y,m.y,b.y);
}
//点p是不是在线段p1 p2 上
bool onSeg(P p1,P p2,P q){
	return crossOp(p1,p2,q)==0&&isMiddle(p1,q,p2);
}
// 点P严格在p1 p2上m先判断三点共线再判断方向 
bool onSeg_strict(P p1,P p2, P q){
	return crossOp(p1,p2,q)==0&&sign((q-p1).dot(p1-p2))*sign((q-p2).dot(p1-p2))<0;
}
// q到直线p1,p2的投影 （垂足） !!!p1==p2的情况 
P proj(P p1,P p2,P q){
	P dir=p2-p1;
	return p1+dir*(dir.dot(q-p1)/dir.abs2());
} 
// q到直线p1,p2的反射 （垂足） !!!p1==p2的情况
P reflect(P p1,P p2, P q){
	return proj(p1,p2,q)*2-q;
}

// 求q到线段p1p2的最小距离
// 先求垂足，判断在不在，不再返回端点 
db nearest(P p1,P p2, P q){
	if(p1==p2) return p1.distTo(q);
	P h=proj(p1,p2,q);
	if(isMiddle(p1,h,p2)) return q.distTo(h);
	return min(p1.distTo(q),p2.distTo(q));
}
// 求两个线段 p1p2线段q1q2的距离 
// 找两个点之间的最小值 
// 直接找两个端点四个距离求个min 
db disSS(P p1,P p2,P q1,P q2){
	if(isSS(p1,p2,q1,q2)) return 0.0;  //相交返回0 
	return min(min(nearest(p1,p2,q1),nearest(p1,p2,q2)),min(nearest(q1,q2,p1),nearest(q1,q2,p2)));
}
// 极角排序 
// 给一些点找这些点按极角大小排序（原点的角度[-PI，PI]）
// atan2() 求度数但是有10-15次方里的误差而且很慢
// 可以用det叉积判断方向 ，一个点在另一个点的方向 这样也不行判段方向会绕一圈
// 先判一个极角是正/负[-PI,0),[0,PI]; 
//	在同一边再用det判断方向 
/*
sort(p,p+n,[&](P &a,P &b){
	int qa=a.quad(),qb=b.quad();
	if(qa!=qb) return qa<qb;
	else  return sign(a.det(b))>0;
})
*/  
// 算凸多边形的面积 
db area(vector<P> ps){
	db ret=0;
	int sz=ps.size();
	for(int i=0;i<sz;i++) ret+=ps[i].det(ps[(i+1)%sz]);
	return ret/2.0; 
}
// 点是不是在多边形上,2表示在里面,1表示在边界，表示在外面 
int contiain(vector<P> ps,P p){
	int n=ps.size(),ret=0;
	for(int i=0;i<n;i++){
		P u=ps[i],v=ps[(i+1)%n];
		if(onSeg(u,v,p)) return 1;
		if(cmp(u.y,v.y)<=0) swap(u,v);
		if(cmp(p.y,u.y)>0||cmp(p.y,v.y)<=0) continue;
		ret^=crossOp(p,u,v)>0;
	}
	return ret*2;
}
// 考虑点在边上的情况 
//算凸包的上下凸壳 ,严格凸包 
vector<P> convexHull(vector<P> ps){
	int n=ps.size();
	if(n<=1) return ps;
	sort(ps.begin(),ps.end()); //正常的按x,y排序 
	vector<P> qs(n*2); //栈 ，共线是不算的 
	int k=0; //栈顶 
	for(int i=0;i<n;qs[k++]=ps[i++])
		while(k>1&&crossOp(qs[k-2],qs[k-1],ps[i])<=0) --k; //判断是不是顺时针方向 ，是顺时针或着共线就弹掉 
	for(int i=n-2,t=k;i>=0;qs[k++]=ps[i--])
		while(k>t&&crossOp(qs[k-2],qs[k-1],ps[i])<=0) --k;
	qs.resize(k-1);//保留前k-1个最后一个重的不要 
	return qs; 
}
// 不严格的凸包，共线也算上 
vector<P> convexHullNonStrict(vector<P> ps){
	//用这个的时候要把点去重一下不然队列里的会有一模一样的点 
	//共线和下一个的乘积一定是0，要去重 
	int n=ps.size();
	if(n<=1) return ps;
	sort(ps.begin(),ps.end()); 
	vector<P> qs(n*2); 
	int k=0; 
	for(int i=0;i<n;qs[k++]=ps[i++])
		while(k>1&&crossOp(qs[k-2],qs[k-1],ps[i])<0) --k;  
	for(int i=n-2,t=k;i>=0;qs[k++]=ps[i--])
		while(k>t&&crossOp(qs[k-2],qs[k-1],ps[i])<0) --k;
	qs.resize(k-1);
	return qs; 	
}
// 一条线把凸多边型分开了 
vector<P> convexCut(const vector<P> &ps,P q1, P q2){
	vector<P> qs;
	int n=ps.size();
	for(int i=0;i<n;i++){
		P p1=ps[i],p2=ps[(i+1)%n];
		int d1=crossOp(q1,q2,p1),d2=crossOp(q1,q2,p2);
		if(d1>=0) qs.push_back(p1);
		if(d1*d2<0) qs.push_back(isLL(p1,p2,q1,q2));
		// 如果确定严格相交就直接把端点放进去 
	}
	return qs;
} 
// 旋转卡壳 （双指针）
// 有一个点集合，希望找到最远（欧几里得距离）的两个点
// 这两个点一定在凸包上 
// 象想有两个平行线在凸多边变行的两端，现在要不停的旋转这个凸多变形
// 我们的全局最远点在某个地方一定会被卡住
// 模拟这个过程即可，双指针卡住 
// 考虑到每个平行的位置 对于两个指针的移动看i和j向量的关系 谁在谁的逆时针方向 
db convexDiameter(vector<P> ps){
	int n=ps.size();
	if(n<=1) return 0;
	int is=0,js=0;
	for(int k=1;k<n;k++) is=ps[k]<ps[is]?k:is,js=ps[js]<ps[k]?k:js; //取最大和最小的 
	int i=is,j=js;
	db ret=(ps[i]-ps[j]).abs2();
	do{
		if((ps[(i+1)%n]-ps[i]).det(ps[(j+1)%n]-ps[j])>=0) (++j)%=n;
		else (++i)%=n;
		ret=max(ret,(ps[i]-ps[j]).abs2());
	}while(i!=is||j!=js);
	return ret;
} 
int main(){
    int n;
    scanf("%d",&n);
    vector<P> a,b;
    for(int i=1;i<=n;i++){
        ll x,y;
        scanf("%lld%lld",&x,&y);
        a.push_back((P){x,y});
    }
    b=convexHull(a);
    long long  t=convexDiameter(b);
    printf("%lld\n",t);
	return 0;
}