POJ 1375 Intervals：解析幾何 + 掃描線算法

題目大意

給定一組圓 (x_i, y_i, r_i) 和一條水平線 y = y0。求水平線與所有圓相交的區間並集，輸出端點坐標。

幾何推導

圓心 (cx, cy)，半徑 r。水平線 y = y0。
垂直距離 d = |cy - y0|。若 d > r 無交點。
交點半弦長 L = √(r² - d²)。
交點 x 坐標：cx ± L。
也可用三角函數：夾角 α = asin(r / dist)，其中 dist = √((cx-x0)² + (cy-y0)²)。
但直接勾股定理更簡單穩定。

掃描線算法

1. 計算每個圓與水平線的交區間 [x_left, x_right]。
2. 將端點標記：左端點 +1，右端點 -1。
3. 所有端點按 x 排序（左端點在前）。
4. 掃描維護計數器 `cnt`：`cnt` 從 0 變 1 輸出左端點；從 1 變 0 輸出右端點。

代碼實現 (C++)

#include 
#include 
#include 
using namespace std;

struct Circle { double x, y, r; };
struct Event { double x; int type; }; // type: +1 入, -1 出

bool cmp(Event a, Event b) {
    if (fabs(a.x - b.x) > 1e-9) return a.x < b.x;
    return a.type > b.type; // 同坐標入優先
}

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
        double x0, y0; scanf("%lf%lf", &x0, &y0);
        Circle c[505];
        for (int i = 0; i < n; i++) scanf("%lf%lf%lf", &c[i].x, &c[i].y, &c[i].r);
        
        Event ev[1010]; int ecnt = 0;
        for (int i = 0; i < n; i++) {
            double dy = fabs(c[i].y - y0);
            if (dy > c[i].r) continue;
            double dx = sqrt(c[i].r * c[i].r - dy * dy);
            ev[ecnt++] = {c[i].x - dx, 1};
            ev[ecnt++] = {c[i].x + dx, -1};
        }
        sort(ev, ev + ecnt, cmp);
        
        int cnt = 0;
        for (int i = 0; i < ecnt; i++) {
            if (cnt == 0 && ev[i].type == 1) printf("%.2f ", ev[i].x);
            cnt += ev[i].type;
            if (cnt == 0 && ev[i].type == -1) printf("%.2f\n", ev[i].x);
        }
        printf("\n");
    }
    return 0;
}

注意事項

• 浮點數比較排序時需考慮精度，`cmp` 中先比 x 再比 type 保證左端點優先。
• 輸出格式：每組數據輸出一行區間端點，端點間空格，區間換行，最後多一空行。
• 勾股定理比三角函數 `asin` 更穩定，避免精度問題。