UVa 10167 Birthday Cake：暴力枚舉分割線

題目大意

平面上 2n 個點（無三點共線），尋找一條過原點的直線 Ax + By = 0，使兩側各恰好 n 個點，且線上無點。A, B ∈ [-500, 500] 整數。

暴力枚舉解法

雙層循環枚舉 A, B ∈ [-500, 500]，對每對 (A,B) 計算所有點的符號 sign(A*x + B*y)。若正負各 n 個且無零值，即為答案。

完整代碼

#include 
using namespace std;
const int MAXN = 110;
int n, x[MAXN], y[MAXN];

bool check(int A, int B) {
    int pos = 0, neg = 0;
    for (int i=0; i<2*n; ++i) {
        int v = A*x[i] + B*y[i];
        if (v > 0) ++pos;
        else if (v < 0) ++neg;
        else return false; // 點在線上
    }
    return pos == n && neg == n;
}

int main() {
    while (cin >> n, n) {
        for (int i=0; i<2*n; ++i) cin >> x[i] >> y[i];
        int A=0, B=0;
        for (int a=-500; a<=500; ++a)
            for (int b=-500; b<=500; ++b)
                if (check(a, b)) { A=a; B=b; goto FOUND; }
        FOUND:
        cout << A << ' ' << B << '\n';
    }
    return 0;
}

複雜度分析

• 枚舉 1001 × 1001 ≈ 10^6 對 (A,B)。
• 每對檢查 2n ≤ 200 個點。
• 總操作 2×10^8，C++ 優化後 < 1s 通過（UVa 時限寬鬆）。

此題展示了「小範圍整數參數暴力枚舉」在幾何分割問題中的實用性，無需複雜幾何算法。