【模板】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);
}
}