UVa 1606 两亲性分子 扫描法 && cnt++的分析

题目传送门

题意

平面上有n个点，每个点为白点或者黑点。现在需放置一条隔板，使得隔板一侧的白点数加上另一侧的黑点数总数最大。隔板上的点可以看做是在任意一侧。

思路

每次可以选取两个点作为隔板，所以我们可以先枚举一个基准点，然后算出其他点关于基准点的相对坐标和关于坐标系的极角（可以用atan2函数来计算，返回与x坐标值的角度），剩下的点依次与基准点形成分隔线，然后将一条直线绕基准点旋转，每当直线扫过一个点，就可以动态修改两侧的点数。
本题还有一个优化的方法，那就是如果该点是黑点，就可以将它的坐标关于基准点旋转180°，这样扫描时就只需要计算一侧的白点数了

代码分析（最后会贴lrj完整代码）

开始看lrj的书的时候发现有一个地方没看懂，如下：

    int    L = 0, R = 0, cnt = 2;   //初始点数设为2，即分隔线上的两个点
    while (L < k)   //每个点都尝试与基点成为分割线
    {
        if (R == L)  { R = (R + 1) % k; cnt++; }  //空区域  **疑惑的地方**
        while (R != L && left(p[L], p[R]))   //R不等于L并且在180度之内
        {
            R = (R + 1) % k;
            cnt++;
        }
        cnt--; //分隔线旋转，原本在分隔线上的点到了右边，所以要减去
        L++;  //分隔线旋转
        ans = max(ans, cnt);
    }

然后翻阅了一下博客，发现比较详细的博客中有详细的代码注释，但是没看到分析的地方，所以我自己思考后想把自己的思路分析写出来和大家分享，如果错误请大家指点。
首先分析L==R成立的情况在什么时候发生？经过分析发现只有一种情况会发生成立，那就是整个循环刚开始进入的时候，L==R==0。这个时候需要将cnt++，因为后面会cnt–，但是这是时候分割线并没有移动，不会涉及到因为分割线移动导致分割线上的点在分割线的右侧，因此需要提前补一个。
其次有一种情况R==L， 那就是基点选的特别完美，所有的点都落在分割线的左侧，这个时候R会一直扫描到L这个起点才结束统计，但是这个时候大循环刚好结束，L会+1，下次循环进入的时候L==R并不成立。
综上只有大循环刚刚进入的时候上面不懂的操作会进入。以后并不会，而刚进入的时候确实需要++(上面已经分析了)。这个疑惑的地方也就解释清楚了。

代码

#include<iostream>  
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

const int maxn = 1000+5;

int n;
int ans;

struct node
{
    int x, y;
    int color;
    double rad;
    bool operator < (const node&rhs) const
    {
        return rad < rhs.rad;
    }
}op[maxn],p[maxn];


bool left(node a, node b)
{
    return a.x*b.y - a.y*b.x >= 0;
}

void solve()
{
    if (n <= 3)  { ans = n; return; }
    ans = 0;
    for (int i = 0; i < n; i++)  //枚举选择基点,一共有n个基点可以选择
    {
        int k = 0;
        for (int j = 0; j < n; j++)    //计算出各个点关于基点的相对坐标
        {
            if (i == j)  continue;
            p[k].x = op[j].x - op[i].x;
            p[k].y = op[j].y - op[i].y;
            if (op[j].color)    //如果为黑点，则可以将它旋转180之后变为白点来计数
            {
                p[k].x = -p[k].x; p[k].y = -p[k].y;
            }
            p[k].rad = atan2(p[k].y, p[k].x);   //求极角,返回角度值
            k++;
        }
        sort(p, p + k);
        //基准点-p[L]为分割线，基准点-p[R]为扫描线
        int    L = 0, R = 0, cnt = 2;   //初始点数设为2，即分隔线上的两个点
        while (L < k)   //每个点都尝试与基点成为分割线
        {
            if (R == L)  { R = (R + 1) % k; cnt++; }  //空区域
            while (R != L && left(p[L], p[R]))   //R不等于L并且在180度之内
            {
                R = (R + 1) % k;
                cnt++;
            }
            cnt--; //分隔线旋转，原本在分隔线上的点到了右边，所以要减去
            L++;  //分隔线旋转
            ans = max(ans, cnt);
        }
    }
}

int main()
{
    //freopen("D:\\txt.txt", "r", stdin);
    while (cin >> n && n)
    {
        for (int i = 0; i < n; i++)
            cin >> op[i].x >> op[i].y >> op[i].color;
        solve();
        cout << ans << endl;
    }
    return 0;
}