UVA 11123 Counting Trapezoids 容斥原理計數平行四邊形

問題

給定 N 個不重合點，求能形成多少個梯形（至少一組對邊平行）。

幾何轉化

梯形 ⇔ 兩條平行線段（不共線、不等長）。

1. 枚舉所有點對構成直線，記錄：斜率 k、長度 len、截距標識 y（或 c/b）
2. 同斜率線段對數 C(cnt,2) 為候選梯形
3. 扣除：共線重疊（同斜率、同截距、長度重疊）與等長平行（平行四邊形/矩形）
4. 容斥：重疊且等長被雙扣，需加回

直線結構與排序

struct Line {
    double len, k, y; // k=atan2(dy,-dx)∈[0,π), y=截距標識
};
bool cmpk(Line a, Line b) { return a.k < b.k; }
bool cmpl(Line a, Line b) { return a.len < b.len; }
bool cmpy(Line a, Line b) { return a.y < b.y; }

容斥計算流程

sort(lines, lines+L, cmpk);
for (每個斜率分組) {
    ans += C(cnt, 2); // 同斜率總對數
    // 扣除共線重疊
    sort(group, cmpl);
    for (每個長度分組) ans -= C(cnt, 2);
    // 扣除等長
    sort(group, cmpy);
    for (每個截距分組) ans -= C(cnt, 2);
    // 加回重疊且等長
    sort(group, cmpy_then_len);
    for (每個截距+長度分組) ans += C(cnt, 2);
}

精度處理

• 斜率用 atan2 避免垂直線無限斜率
• 截距用 c/b 或 c/a，垂直線用 x 截距
• 雙精度比較 fabs(a-b) < 1e-9