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

2018.10.18 poj2187Beauty Contest(旋转卡壳)

程序员文章站 2022-04-01 15:50:40
...

传送门
旋转卡壳板子题。
就是求凸包上最远点对。


直接上双指针维护旋转卡壳就行了。
注意要时刻更新最大值。
代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 50005
using namespace std;
inline int read(){
	int ans=0,w=1;
	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans*w;
}
int n,q[N],top=0;
int ans=0.0;
struct pot{
	int x,y;
	inline pot operator-(const pot&a){return (pot){x-a.x,y-a.y};}
	inline int operator^(const pot&a){return x*a.y-y*a.x;}
	inline int dist(){return x*x+y*y;}
}p[N];
inline bool cmp(pot a,pot b){
	int ret=(a-p[1])^(b-p[1]);
	if(ret!=0)return ret>=0;
	return a.dist()<b.dist();
}
inline void graham(){
	int tmp=1;
	for(int i=2;i<=n;++i)if(p[i].x<p[tmp].x||(p[i].x==p[tmp].x&&p[i].y<p[tmp].y))tmp=i;
	if(tmp^1)swap(p[tmp],p[1]);
	sort(p+2,p+n+1,cmp),q[++top]=1;
	for(int i=2;i<=n;++i){
		while(top>=2&&((p[i]-p[q[top-1]])^(p[q[top]]-p[q[top-1]]))>=0)--top;
		q[++top]=i;
	}
}
int main(){
	n=read();
	for(int i=1;i<=n;++i)p[i].x=read(),p[i].y=read();
	graham();
	if(top==2)return cout<<(p[q[top]]-p[q[top-1]]).dist(),0;
	q[++top]=1;
	for(int i=1,j=3;i<=top;++i){
		while(i%top+1!=j&&((p[q[i+1]]-p[q[i]])^(p[q[j]]-p[q[i]]))<=((p[q[i+1]]-p[q[i]])^(p[q[j+1]]-p[q[i]])))j=j%top+1;
		ans=max(ans,(p[q[j]]-p[q[i]]).dist()),ans=max(ans,(p[q[j]]-p[q[i+1]]).dist());
	}
	cout<<ans;
	return 0;
}
相关标签: 计算几何