POJ1737 Connected Graph 高精度+递推

POJ2187 Beauty Contest 计算几何+旋转卡壳

shinbokuow posted @ Feb 13, 2015 11:39:06 PM in POJ with tags 计算几何 旋转卡壳 , 19584 阅读

思路:

本人自己写了一个傻逼的不能再傻逼的御用凸包模板,谁要是扒的话简直就是作死...

然后这道题目主要就是利用旋转卡壳寻找对踵点,然后更新答案.

然后旋转卡壳非常牛逼是\(O(n)\)的.这是为什么呢?

对于凸包上的每一条边,对踵点与这条边形成的三角形的面积必定最大.因此,这条边之外的点是成一个单峰函数分布的.

此外我们还很容易从凸包上得到单调性.

利用这两个性质,就很容易做到凸包上的线性扫描了.

#include<set>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define N 50010

struct Point{
	int x,y;
	Point(){}
	Point(int _x,int _y):x(_x),y(_y){}
	bool operator<(const Point&B)const{return(x<B.x)||(x==B.x&&y>B.y);}
	Point operator+(const Point&B)const{return Point(x+B.x,y+B.y);}
	Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);}
}P[N];int cnt;
inline int Cross(const Point&a,const Point&b){return a.x*b.y-a.y*b.x;}
inline int sqr(int x){return x*x;}
inline int dis2(const Point&a,const Point&b){return sqr(a.x-b.x)+sqr(a.y-b.y);}
set<Point>S;

Point stk[N];int top;

#define f(x) (x>top?1:x)
int main(){
	//freopen("tt.in","r",stdin);
	int n;scanf("%d",&n);register int i,j;
	
	if(n<=1){puts("0");return 0;}
	
	int x,y;
	while(n--){scanf("%d%d",&x,&y);if(S.find(Point(x,y))==S.end())S.insert(Point(x,y)),P[++cnt]=Point(x,y);}
	
	sort(P+1,P+cnt+1);
	
	bool allline=1;
	for(i=1;i+2<=cnt;++i)if(Cross(P[i]-P[i+1],P[i+1]-P[i+2])!=0)allline=0;
	if(allline){printf("%d",dis2(P[1],P[cnt]));return 0;}
	
	int revins;for(revins=cnt;revins!=1&&P[revins].x==P[revins-1].x;--revins);
	for(i=revins;i<=(n+revins)/2;++i)swap(P[i],P[n+revins-i]);
	
	for(i=1;i<=cnt;++i){
		if(!top)stk[++top]=P[i];
		else{while(top>1&&(P[i].y-stk[top].y)*(stk[top].x-stk[top-1].x)<=(stk[top].y-stk[top-1].y)*(P[i].x-stk[top].x))--top;stk[++top]=P[i];}
	}
	int nowtop=top;
	for(i=revins-1;i>=1;--i){
		if(top==nowtop)stk[++top]=P[i];
		else{while(top>nowtop+1&&(P[i].y-stk[top].y)*(stk[top].x-stk[top-1].x)<=(stk[top].y-stk[top-1].y)*(P[i].x-stk[top].x))--top;stk[++top]=P[i];}
	}--top;
	
	int r=2,res=0;
	for(i=1;i<=top;++i){
		while(Cross(stk[i]-stk[f(i+1)],stk[i]-stk[r])<=Cross(stk[i]-stk[f(i+1)],stk[i]-stk[f(r+1)]))r=f(r+1);
		res=max(res,dis2(stk[i],stk[r]));
		res=max(res,dis2(stk[f(i+1)],stk[r]));
	}
	
	printf("%d",res);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter