ZOJ 3575 Under Attack III：橢圓覆蓋最多城市點的幾何轉換與枚舉

題目重述

給定橢圓長軸 a、短軸 b（平行於坐標軸）與 n ≤ 200 個城市座標（非負浮點數），橢圓可平移至任意位置，邊界點視為被覆蓋。求橢圓最多能覆蓋多少城市。

核心技巧：仿射變換將橢圓轉為單位圓

橢圓方程 (x/a)² + (y/b)² ≤ 1。對所有點做縮放變換：
X = x / a, Y = y / b
原橢圓即變為以原點為圓心、半徑為 1 的單位圓；城市點同步變換為 (Xᵢ, Yᵢ)。問題轉化為：單位圓平移後最多覆蓋多少變換後的點。

最優圓心必經過兩點

若最優圓覆蓋 ≥ 2 個點，則一定存在一個同樣覆蓋這些點的圓，其圓心由其中兩點決定（兩點到圓心距離均為 1）。因此只需枚舉所有點對 (i, j)：

1. 若兩點距離 d > 2，無法同時被半徑 1 圓覆蓋，跳過。
2. 否則計算中點 M，垂直於 PᵢPⱼ 方向兩側各有一個候選圓心 O = M ± h * perp，其中 h = √(1 - (d/2)²)。
3. 對每個候選圓心，掃描所有點計數覆蓋數，更新全局最大值。

特殊情況：若任意兩點距離均 > 2，答案退化為 1（至少能覆蓋單個點）。

複雜度分析

• 點對枚舉 O(n²)，每對驗證 O(n)，總 O(n³) = 8×10⁶，極易在 7 秒內通過。
• 無需三重迴圈優化，常數極小。

關鍵實作細節

• 輸入為多組測資，EOF 結束；a, b 為浮點數。
• 距離比較加 eps = 1e-6 容差，避免浮點誤差導致 d > 2 錯判。
• 原碼中 solve 函數重名導致遞迴，建議改名 countCover；且 ans 初始化應為 1 而非 0，以正確處理「全點兩兩距離 > 2」的情況。

修正後核心邏輯（偽碼）

ans = 1
for i in 0..n-1:
    for j in i+1..n-1:
        d = dist(P[i], P[j])
        if d > 2 + eps: continue
        mid = (P[i] + P[j]) / 2
        h = sqrt(max(0, 1 - (d/2)^2))
        dir = normalize(rotate90(P[j] - P[i]))
        for sign in {+1, -1}:
            O = mid + sign * h * dir
            cnt = count points with dist(O, P[k]) ≤ 1 + eps
            ans = max(ans, cnt)
print ans

總結

本題展示了「幾何變換規範化問題」+「最優解構造性質（圓心由兩點決定）」+「暴力枚舉驗證」的標準解題套路。對於 n ≤ 200 的小規模幾何覆蓋問題，O(n³) 枚舉往往足夠且最不易出錯。