uva1606

//枚举基准点 其余点按极角排序之后按大小枚举 成为分割线 扫描
//枚举的时候计算两侧的黑白点数目 规定逆时针旋转 并统计右侧的白点 左侧的黑点
//统计黑点的策略 由于黑白点有对称性 于是可以把黑点关于基准点对称过去变为白点 这样只需统计右侧的白点即可
#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;
}

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 最近有一个任务,从页面中抓取页面中所有的链接,当然使用PHP正则表达式是最方便的办法。要写出正则表达式,就要先总结...
    Talentisan阅读 928评论 0 0
  • 通缉人员的设备不定时向四周发射线索信号,形成快速破案的方法?
    邢乐的简书阅读 187评论 0 0
  • 前几天,有一个舞蹈,只练了一个晚上。第二天就考试,那天晚上,回到宿舍,没有洗澡在那里和舍友一起练到差不多关灯才罢 ...
    心情小屋阅读 168评论 0 0
  • 今天抽到太阳~ 读牌1 蓝色的太空下,一轮大大的太阳,散发着光芒。太阳中心是一张人的脸。 读牌2 砖砌成的矮墙,墙...
    Yvonne伊芳阅读 214评论 0 0