UVa 1606 Amphiphilic Carbon Molecules （扫描法+极角排序）

题意：平面上有 n 个点，每个点不是黑的就是白的，现在要放一个隔板，把它们分成两部分，使得一侧的白点数加上另一侧的黑点数最多。

析：这个题很容易想到的就是暴力，不妨假设隔板至少经过两个点，即使不经过也可以通过平移使它经过，然后每次枚举两个点，当作隔板，枚举量是n*n，

然后计算是 n，那么时间复杂度就是 n ，一定会超时的，我产可以这样想，先枚举一个点，然后绕这个点旋转，每扫过一个点，就动态修改两侧的点数，

在转一周过程中，每个点至多扫到两次，这个过程复杂是 n，扫描前进行极角，时间复杂度是 n*logn。这个题为了精度最好是叉乘来判。

可以利用中心对称来简化运算。

代码如下：

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <vector>

#include <set>

#include <cstring>

#include <cmath>

using namespace std;

const int maxn = 1000 + 5;

struct node{

    int x, y;

    double rad;//极角

    node(int xx = 0, int yy = 0) : x(xx), y(yy) { }

    void inverse(){  x = -x;  y = -y;  }

    void cal(){  rad = atan2(y, x);  }

    bool operator < (const node &p) const{//排序

        return rad < p.rad;

    }

    friend node operator - (const node &lhs, const node &rhs){//减法

        return node(lhs.x-rhs.x, lhs.y-rhs.y);

    }

};

node a[maxn];

int col[maxn], n;

int cross(const node &p, const node &q){//叉乘

    return p.x * q.y - p.y * q.x;

}

int solve(){

    int ans = 0;

    for(int i = 0; i < n; ++i){

        vector<node> v;

        for(int j = 0; j < n; ++j){

            if(i == j)   continue;

            node temp = a[i] - a[j];//看成是向量

            if(col[j])  temp.inverse();//利用中心对称

            temp.cal();//计算极角

            v.push_back(temp);

        }

        sort(v.begin(), v.end());

        int cnt = 2, r = 0, m = v.size();

        for(int l = 0; l < m; ++l){//开始扫描

            if(l == r){ r = (r+1) % m;  ++cnt;  }

            while(l != r && cross(v[l], v[r]) >= 0){  ++cnt;  r = (r+1) % m; }

            --cnt;

            ans = max(ans, cnt);

        }

    }

    return ans;

}

int main(){

    while(scanf("%d", &n) == 1 && n){

        for(int i = 0; i < n; ++i)  scanf("%d %d %d", &a[i].x, &a[i].y, &col[i]);

        printf("%d\n", solve());

    }

    return 0;

}