問題背景

給定一個光源點與若干圓形障礙物，求光源在 Y 軸上的投影區間。每個圓會產生兩條切線，切線與 Y 軸的交點決定該圓的投影區段；多個區段可能重疊，最終需輸出合併後的不重疊投影區間。

幾何推導

1. 設光源為 P，圓心為 Q，半徑 r，PQ 距離為 d。
2. ∠a = asin(r / d)（半徑與連心線夾角）
3. ∠b = asin(|P.x - Q.x| / d)（連心線與 Y 軸夾角）
4. 兩條切線與 Y 軸夾角分別為 a + b 與 b - a。
5. 利用切線斜率 tan(角度) 計算交點座標，得到區間 [L, R]。

算法流程

1. 對每個圓計算其投影區間 [l, r]。
2. 按左端點 l 升序排序。
3. 掃描合併重疊區間：維護當前合併區間 [L, R]，若下一區間 l ≤ R 則 R = max(R, r)；否則輸出 [L, R] 並更新為新區間。

核心代碼片段

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

struct Point { double x, y; } P, Q;
struct Seg { double l, r; } seg[505];

double dist(Point a, Point b) {
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

bool cmp(Seg a, Seg b) { return a.l < b.l; }

int main() {
    int n;
    while (cin >> n) {
        cin >> P.x >> P.y;
        for (int i = 0; i < n; ++i) {
            cin >> Q.x >> Q.y >> r;
            double d = dist(P, Q);
            double a = asin(r / d);
            double b = asin(fabs(P.x - Q.x) / d);
            double ang1 = a + b, ang2 = b - a;
            seg[i].l = P.x - P.y * tan(ang1);
            seg[i].r = P.x - P.y * tan(ang2);
            if (seg[i].l > seg[i].r) swap(seg[i].l, seg[i].r);
        }
        sort(seg, seg + n, cmp);
        double L = seg[0].l, R = seg[0].r;
        for (int i = 1; i < n; ++i) {
            if (seg[i].l <= R) R = max(R, seg[i].r);
            else {
                printf("%.2f %.2f\n", L, R);
                L = seg[i].l; R = seg[i].r;
            }
        }
        printf("%.2f %.2f\n\n", L, R);
    }
    return 0;
}

關鍵點提示

• 角度計算需處理象限，使用 atan2 更穩健。
• 切線可能垂直（斜率無窮大），需單獨判斷 P.y == Q.y 情況。
• 輸出格式要求保留兩位小數，區間之間空行分隔。