欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ2187(旋转卡壳)

程序员文章站 2022-03-30 09:40:21
...

你的快乐老家

令人窒息啊

知乎上说“旋转卡壳”有24种读法

感觉好可怕啊

旋转卡壳模板题

求出凸包后

通过不断的枚举当前的边和对面的点不断得到更优的解

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<iostream>
#include<stdio.h>
#include<cstdlib>
using namespace std;
int n,m,ans;
inline int read(){
	char ch=getchar();
	int res=0;
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
	return res;
};
struct point{
	int x,y;
	point(){}
	point(int a,int b):
		x(a),y(b){};
	friend inline point operator -(const point &a,const point &b){
		return point(a.x-b.x,a.y-b.y);
	}
	friend inline int operator *(const point &a,const point &b){
		return a.x*b.y-a.y*b.x;
	}
	inline int calc(){
		return x*x+y*y;
	}
}p[50005],q[50005];
inline bool comp(point a,point b){
	int res=(a-p[1])*(b-p[1]);
	if(res!=0)return res>0;
	return a.calc()<b.calc();
}
inline void graham(){
	int dat=1;
	for(int i=2;i<=n;i++){
		if(p[i].x<p[dat].x||(p[i].x==p[dat].x&&p[i].y<p[dat].y)){
			dat=i;
		}
	}
	if(dat!=1) swap(p[dat],p[1]);
	sort(p+2,p+1+n,comp);
	q[++m]=p[1];
	for(int i=2;i<=n;i++){
		while(m>=2&&((p[i]-q[m-1])*(q[m]-q[m-1])>=0))m--;
		q[++m]=p[i];
	}
}
inline int area(point a,point b,point c){
	return (b-a)*(c-a);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y;
	graham();
	if(m==2) {
		cout<<(q[2]-q[1]).calc();
		return 0;
	}
	q[m+1]=q[1];
	for(int i=1,j=3;i<=m;i++){
		while((j)%m+1!=i&&area(q[i],q[i+1],q[j])<=area(q[i],q[i+1],q[j+1])) j=(j)%m+1;
		ans=max(ans,(q[j]-q[i]).calc());
		ans=max(ans,(q[j]-q[i+1]).calc());
	}
	cout<<ans<<'\n';
}