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

【模板】UVA1606 两亲性分子(极角扫描法)

程序员文章站 2022-03-29 21:53:17
...

【模板】UVA1606 两亲性分子(极角扫描法)

题意:

思路:

极角扫描法的思想是这样的:首先,选择一个点作为基准点,然后求出其他点相对于该基准点的相对坐标,同时求出相对坐标系下的极角。对这些点按照极角由小到大排序。设L=0,R=0,那么每次都以O-p[L]这条线为分隔线,O-p[R]作为扫描线,用cnt来统计在分隔线左侧的点的个数(包括分隔线上的点)。看p[R]这个点是否在分隔线的左侧,如果是,R=(R+1)%k,cnt++。一直让O-p[R]这条扫描线转到刚刚超过180度时候停止,然后L++,cnt–,表示分隔线旋转,原来在分隔线的点成为了分隔线右侧的点了。

不过本题还运用了以下等效的思想,因为统计的是一侧的黑点+另一侧的白点数,不妨在算相对坐标时候把黑点换成白点,并将它旋转180度处理,这样就转化为统计一侧白点的数目了。另一个技巧是判断一个点是否在分隔线左侧利用Cross来判断,不会产生精度问题。

本题选基准点有O(N)种,对点按照极角排序时间是O(NlogN),扫描时候的复杂度是O(N),因此总的时间复杂度是O(N^2 logN+N^2)。可以看做O(N ^2logN)处理。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6;
int n,col[maxn];
struct node{
	int x,y;
	double rad;
}p[maxn],np[maxn];

bool cmp(node a,node b){
	return a.rad<b.rad;
}
bool check(node a,node b){
	return a.x*b.y-a.y*b.x>=0;
} 
int get(int x){
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(i==x)continue;
		np[++cnt].x=p[i].x-p[x].x;
		np[cnt].y=p[i].y-p[x].y;
		if(col[i]){
			np[cnt].y*=-1;
			np[cnt].x*=-1;
		}
		np[cnt].rad=atan2(np[cnt].y,np[cnt].x);
	}
	sort(np+1,np+1+cnt,cmp);
	int L=1,R=1,mx=0,ans=2;
	while(L<=cnt){
		if(R==L)R=(R%cnt)+1,++ans;
		while(R!=L&&check(np[L],np[R])){
			R=(R%cnt)+1,++ans;
		}
		++L,ans--;
		mx=max(ans,mx);
	}
	return mx;
}
int main(){
	while(scanf("%d",&n)&&n){
		for(int i=1;i<=n;i++){
			scanf("%d%d%d",&p[i].x,&p[i].y,&col[i]);
		}
		int ans=2;
		for(int i=1;i<=n;i++){
			ans=max(ans,get(i));
		}
		printf("%d\n",ans);
	}
} 
相关标签: 计算几何