uva1606

作者: Amosasas | 来源:发表于2017-11-19 23:26 被阅读0次
//枚举基准点 其余点按极角排序之后按大小枚举 成为分割线 扫描
//枚举的时候计算两侧的黑白点数目 规定逆时针旋转 并统计右侧的白点 左侧的黑点
//统计黑点的策略 由于黑白点有对称性 于是可以把黑点关于基准点对称过去变为白点 这样只需统计右侧的白点即可
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;

const int maxn = 1000 + 5;
struct Point{
    int x, y;
    double rad;
    bool operator < (const Point& rhs) const{
        return rad < rhs.rad;
    };
};
Point p[maxn], op[maxn];
int n, color[maxn];

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


int solve(){
    int ans = -1;
    for(int i = 0; i < n; i++){          //枚举基准点
        int k = 0;
        for(int j = 0; j < n; j++){      //计算关于基准点的坐标
            if(i != j){
                p[k].x = op[j].x - op[i].x;
                p[k].y = op[j].y - op[i].y;
                if(color[j]){            //对称黑点
                    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);
        int L = 0, R = 0, cnt = 2;
        while(L < k){
            if(L == R){
                R = (R+1) % k;
                cnt++;
            }
            while( turnLeft(p[L], p[R]) && L != R){
                R = (R+1) % k;
                cnt++;
            }
            cnt--;
            ans = max(ans, cnt);
            L++;
        }
    }
    return ans;
}

int main(){
    while(scanf("%d", &n) && n){
        for(int i = 0; i < n; i++){
            scanf("%d %d %d", &op[i].x, &op[i].y, &color[i]);
        }
        printf("%d\n", solve());
    }
    return 0;
}

相关文章

网友评论

      本文标题:uva1606

      本文链接:https://www.haomeiwen.com/subject/xlkmvxtx.html