//枚举基准点 其余点按极角排序之后按大小枚举 成为分割线 扫描
//枚举的时候计算两侧的黑白点数目 规定逆时针旋转 并统计右侧的白点 左侧的黑点
//统计黑点的策略 由于黑白点有对称性 于是可以把黑点关于基准点对称过去变为白点 这样只需统计右侧的白点即可
#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
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...