UVA - 1606 Amphiphilic Carbon Molecules（两亲性分子）（扫描法）

#pragma comment(linker, "/STACK:102400000, 102400000")
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
#define Min(a, b) ((a < b) ? a : b)
#define Max(a, b) ((a < b) ? b : a)
typedef long long LL;
typedef unsigned long long ULL;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const double eps = 1e-8;
const int MAXN = 1000 + 10;
const int MAXT = 10000 + 10;
using namespace std;
struct Point{
    int x, y;
    double r;
    bool operator < (const Point& rhs)const{
        return r < rhs.r;
    }
}num[MAXN], tmp[MAXN];
int color[MAXN];
bool Left(Point A, Point B){
    return A.x * B.y - A.y * B.x >= 0;
}
int main(){
    int n;
    while(scanf("%d", &n) == 1){
        if(!n) return 0;
        for(int i = 0; i < n; ++i){
            scanf("%d%d%d", &num[i].x, &num[i].y, &color[i]);
        }
        if(n <= 3){
            printf("%d\n", n);
            continue;
        }
        int ans = 0;
        for(int i = 0; i < n; ++i){//以i为基准点
            int id = 0;
            for(int j = 0; j < n; ++j){
                if(i != j){
                    tmp[id].x = num[j].x - num[i].x;
                    tmp[id].y = num[j].y - num[i].y;
                    if(color[j]){//遇到黑点的时候将其旋转180°，这样可以将统计一侧黑点和一侧白点转化为统计所有白点
                        tmp[id].x = -tmp[id].x;
                        tmp[id].y = -tmp[id].y;
                    }
                    tmp[id].r = atan2(tmp[id].y, tmp[id].x);
                    ++id;
                }
            }
            sort(tmp, tmp + id);
            int l = 0, r = 0, cnt = 2;
            while(l < id){
                if(r == l){
                    r = (r + 1) % id;
                    ++cnt;
                }
                while(r != l && Left(tmp[l], tmp[r])){
                    r = (r + 1) % id;
                    ++cnt;
                }
                --cnt;
                ++l;
                ans = Max(ans, cnt);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}