例题 8-6 两亲性分子（Amphiphilic Carbon Molecules, ACM/ICPC Shanghai 2004, UVa1606）

原题链接：https://vjudge.net/problem/UVA-1606
分类：扫描法
备注：极角扫描法

几何不好，极角扫描这块还是很难理解。
主要是if(pcur==prot)的情况，除了开始以外，也可能再次出现，如果不管的话，while这行就不能正确运行。
再次出现的情况，就是新的隔板和原隔板的答案是相同的，一增一减就没有了变化。

感谢博文：https://blog.csdn.net/qq_40738840/article/details/104618218

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
const double pi=acos(-1.0);
int n;
struct Point{
    int x,y,r;
    double theta;
    bool operator < (const Point& b){
        return theta<b.theta;
    }
}p[maxn],p2[maxn];
bool isLeft(const Point&a,const Point& b){//O-b在O-a线段的左边
    return a.x*b.y-a.y*b.x>=0;
}
int main(void){
    //freopen("in.txt","r",stdin);
    while(~scanf("%d",&n)&&n){
        for(int i=0;i<n;i++)scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].r);
        if(n<=3){printf("%d\n",n);continue;}
        int ans=0;
        for(int i=0;i<n;i++){//p[i]作为基点
            int pos=0;
            for(int j=0;j<n;j++){//p[i]-p[j]作为隔板
                if(i==j)continue;
                p2[pos].x=p[j].x-p[i].x;
                p2[pos].y=p[j].y-p[i].y;
                if(p[j].r==1){p2[pos].x*=-1; p2[pos].y*=-1;}
                p2[pos].theta=atan2(p2[pos].y,p2[pos].x);
                pos++;
            }
            sort(p2,p2+pos);
            int cnt=2,prot=0;//pcur是隔板，prot是在一侧要扫描的点
            for(int pcur=0;pcur<pos;pcur++){
                if(pcur==prot)prot=(prot+1)%pos,cnt++;
                //如果if成立且这点不在左侧，则下面的while直接跳过,cnt会减回来
                //如果在左侧，下面的while则多计数一次，同样要减回来
                while(pcur!=prot&&isLeft(p2[pcur],p2[prot]))prot=(prot+1)%pos,cnt++;
                cnt--;//如果没触发第一个if，那么cnt加上的数量是正常的，但是pcur动了，cnt要减一
                //如果触发了第一个if，pcur也动了，说明两个轴的答案相同，一增一减
                ans=max(ans,cnt);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}