//枚舉基準(zhǔn)點(diǎn) 其余點(diǎn)按極角排序之后按大小枚舉 成為分割線 掃描
//枚舉的時(shí)候計(jì)算兩側(cè)的黑白點(diǎn)數(shù)目 規(guī)定逆時(shí)針旋轉(zhuǎn) 并統(tǒng)計(jì)右側(cè)的白點(diǎn) 左側(cè)的黑點(diǎn)
//統(tǒng)計(jì)黑點(diǎn)的策略 由于黑白點(diǎn)有對稱性 于是可以把黑點(diǎn)關(guān)于基準(zhǔn)點(diǎn)對稱過去變?yōu)榘c(diǎn) 這樣只需統(tǒng)計(jì)右側(cè)的白點(diǎn)即可
#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)點(diǎn)
int k = 0;
for(int j = 0; j < n; j++){ //計(jì)算關(guān)于基準(zhǔn)點(diǎ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]){ //對稱黑點(diǎn)
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)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點(diǎn),簡書系信息發(fā)布平臺,僅提供信息存儲(chǔ)服務(wù)。
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點(diǎn),簡書系信息發(fā)布平臺,僅提供信息存儲(chǔ)服務(wù)。
相關(guān)閱讀更多精彩內(nèi)容
- 最近有一個(gè)任務(wù),從頁面中抓取頁面中所有的鏈接,當(dāng)然使用PHP正則表達(dá)式是最方便的辦法。要寫出正則表達(dá)式,就要先總結(jié)...
- 前幾天,有一個(gè)舞蹈,只練了一個(gè)晚上。第二天就考試,那天晚上,回到宿舍,沒有洗澡在那里和舍友一起練到差不多關(guān)燈才罷 ...
- 今天抽到太陽~ 讀牌1 藍(lán)色的太空下,一輪大大的太陽,散發(fā)著光芒。太陽中心是一張人的臉。 讀牌2 磚砌成的矮墻,墻...