uva1606

//枚舉基準(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;
}

?著作權(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ù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 最近有一個(gè)任務(wù),從頁面中抓取頁面中所有的鏈接,當(dāng)然使用PHP正則表達(dá)式是最方便的辦法。要寫出正則表達(dá)式,就要先總結(jié)...
    Talentisan閱讀 972評論 0 0
  • 通緝?nèi)藛T的設(shè)備不定時(shí)向四周發(fā)射線索信號,形成快速破案的方法?
    邢樂的簡書閱讀 214評論 0 0
  • 前幾天,有一個(gè)舞蹈,只練了一個(gè)晚上。第二天就考試,那天晚上,回到宿舍,沒有洗澡在那里和舍友一起練到差不多關(guān)燈才罷 ...
    心情小屋閱讀 185評論 0 0
  • 今天抽到太陽~ 讀牌1 藍(lán)色的太空下,一輪大大的太陽,散發(fā)著光芒。太陽中心是一張人的臉。 讀牌2 磚砌成的矮墻,墻...
    Yvonne伊芳閱讀 279評論 0 0

友情鏈接更多精彩內(nèi)容