//枚舉基準(zhǔn)點 其余點按極角排序之后按大小枚舉 成為分割線 掃描
//枚舉的時候計算兩側(cè)的黑白點數(shù)目 規(guī)定逆時針旋轉(zhuǎn) 并統(tǒng)計右側(cè)的白點 左側(cè)的黑點
//統(tǒng)計黑點的策略 由于黑白點有對稱性 于是可以把黑點關(guān)于基準(zhǔn)點對稱過去變?yōu)榘c 這樣只需統(tǒng)計右側(cè)的白點即可
#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++){ //枚舉基準(zhǔn)點
int k = 0;
for(int j = 0; j < n; j++){ //計算關(guān)于基準(zhǔn)點的坐標(biāo)
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
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來庐杨，“玉大人选调，你說我怎么就攤上這事×榉荩” “怎么了仁堪？”我有些...
- 文/不壞的土叔 我叫張陵，是天一觀的道長填渠。 經(jīng)常有香客問我弦聂，道長，這世上最難降的妖魔是什么氛什？ 我笑而不...
- 正文 為了忘掉前任横浑，我火速辦了婚禮，結(jié)果婚禮上屉更，老公的妹妹穿的比我還像新娘徙融。我一直安慰自己，他們只是感情好瑰谜，可當(dāng)我...
- 文/花漫 我一把揭開白布欺冀。 她就那樣靜靜地躺著树绩，像睡著了一般。 火紅的嫁衣襯著肌膚如雪隐轩。 梳的紋絲不亂的頭發(fā)上饺饭，一...
- 文/蒼蘭香墨 我猛地睜開眼积瞒，長吁一口氣：“原來是場噩夢啊……” “哼川尖！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起茫孔，我...
- 正文 年R本政府宣布，位于F島的核電站妇菱，受9級特大地震影響承粤，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜闯团，卻給世界環(huán)境...
- 文/蒙蒙 一辛臊、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧房交，春花似錦彻舰、人聲如沸。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽隔心。三九已至，卻和暖如春尚胞，著一層夾襖步出監(jiān)牢的瞬間硬霍，已是汗流浹背。 一陣腳步聲響...
推薦閱讀更多精彩內(nèi)容
- 最近有一個任務(wù)，從頁面中抓取頁面中所有的鏈接胯甩，當(dāng)然使用PHP正則表達(dá)式是最方便的辦法昧廷。要寫出正則表達(dá)式，就要先總結(jié)...
- 今天抽到太陽~ 讀牌1 藍(lán)色的太空下，一輪大大的太陽副硅，散發(fā)著光芒姥宝。太陽中心是一張人的臉。 讀牌2 磚砌成的矮墻恐疲，墻...
