HDU 2857 Mirror and Light：計算幾何求對稱點與直線交點

問題描述

給定鏡子線段 (兩點 M1, M2 確定直線)、光源 L1、光線反射方向點 L2（即光線從 L1 射向鏡子，反射後經過 L2）。求光線在鏡面上的反射點。

幾何關係

光路可逆性：反射點 P 滿足 L1 關於鏡面直線的對稱點 L1'、P、L2 共線。
即：P = Line(L1', L2) ∩ Line(M1, M2)。

核心子問題

1. 點關於直線的對稱點
2. 兩直線交點

模板一：斜率法（需處理垂直/水平特判）

Point symmetric(Point p, Point l1, Point l2) {
    if (fabs(l1.x - l2.x) < EPS) { // 垂直線
        return {2*l1.x - p.x, p.y};
    }
    double k = (l1.y - l2.y) / (l1.x - l2.x);
    if (fabs(k) < EPS) { // 水平線
        return {p.x, 2*l1.y - p.y};
    }
    // 一般情況：對稱點公式推導
    double x = (2*k*k*l1.x + 2*k*p.y - 2*k*l1.y - k*k*p.x + p.x) / (1 + k*k);
    double y = p.y - (x - p.x) / k;
    return {x, y};
}

Point intersection(Point u1, Point u2, Point v1, Point v2) {
    // 參數法：u1 + t*(u2-u1) = v1 + s*(v2-v1)
    double t = ((u1.x-v1.x)*(v1.y-v2.y) - (u1.y-v1.y)*(v1.x-v2.x))
             / ((u1.x-u2.x)*(v1.y-v2.y) - (u1.y-u2.y)*(v1.x-v2.x));
    return {u1.x + t*(u2.x-u1.x), u1.y + t*(u2.y-u1.y)};
}

模板二：向量投影法（無需特判斜率，更穩健）

// 點 p 到直線 l1-l2 的垂足
Point foot(Point p, Point l1, Point l2) {
    Point t = {p.x + l1.y - l2.y, p.y + l2.x - l1.x}; // 垂線方向向量
    return intersection(p, t, l1, l2);
}

Point symmetric(Point p, Point l1, Point l2) {
    Point f = foot(p, l1, l2);
    return {2*f.x - p.x, 2*f.y - p.y}; // 對稱點 = 2*垂足 - 原點
}

完整程式碼（C++）

/* HDU 2857 Mirror and Light */
#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-8;

struct Point { double x, y; };

Point intersection(Point u1, Point u2, Point v1, Point v2) {
    double t = ((u1.x-v1.x)*(v1.y-v2.y) - (u1.y-v1.y)*(v1.x-v2.x))
             / ((u1.x-u2.x)*(v1.y-v2.y) - (u1.y-u2.y)*(v1.x-v2.x));
    return {u1.x + t*(u2.x-u1.x), u1.y + t*(u2.y-u1.y)};
}

Point foot(Point p, Point l1, Point l2) {
    Point t = {p.x + l1.y - l2.y, p.y + l2.x - l1.x};
    return intersection(p, t, l1, l2);
}

Point symmetric(Point p, Point l1, Point l2) {
    Point f = foot(p, l1, l2);
    return {2*f.x - p.x, 2*f.y - p.y};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        Point m1, m2, l1, l2;
        cin >> m1.x >> m1.y >> m2.x >> m2.y >> l1.x >> l1.y >> l2.x >> l2.y;
        Point l1p = symmetric(l1, m1, m2);
        Point ans = intersection(l1p, l2, m1, m2);
        cout << fixed << setprecision(3) << ans.x << " " << ans.y << "\n";
    }
    return 0;
}

關鍵點

• 向量投影法 避免斜率無限大/零的特判，代碼更簡潔、數值穩定。
• 參數法求交點：通用、不退化（平行情況題目保證不發生）。
• 輸出保留 3 位小數 fixed << setprecision(3)。

總結

HDU 2857 是計算幾何基礎模板題：對稱點 + 直線交點。掌握向量投影法求垂足可統一處理所有直線情況，無需分類討論斜率。此兩模板（垂足/對稱點、兩直線交點）是計算幾何必備工具箱核心組件。