PKU 2036 I Conduit!

題意：

在白紙上要畫 N (≤ 10000) 條線段 (Straight line segment)，問總共最少要畫多少筆

---

解1：

排序→掃描 (Vector Arithmetic)

出現在同一筆的線段，必然有同樣的斜率（或角度）
對於相同斜率但不共線的線段
它們與原點（或任意 Fixed 的一點）有不同的距離

我們可以對每條 Segment a→b (限定 a < b)
定義以下的 struct：

struct E { // 線段 a→b

    Pt a, b, dir;

    double distToOrigin;

    double t1, t2;

};

其中
a = Start
b = End
dir = ab 的 單位向量
distToOrigin = 把線段無限延伸後，與原點的垂直距離
t1 = a 在 dir 方向上投影
t2 = b 在 dir 方向上投影

然後按
方向(dir) → 與原點距離(distToOrigin) → 投影(t1)
排序

由陣列開端掃描
一邊把 v 及 distToOrigin 相同的線段 merge 起來
統計答案

時間複雜度 O(N lg N)

---

解2：

GAGGUY 的排序方法同樣是排序→掃描
他應用了 equation 的方法
可以減省 code length

具體說明如下：

對每條線段，求出 斜率-截距 式（Slope-intercept form）y = mx + c
然後按
斜率(m) → y-截距(c) → 線段中 x-座標較小者
排序掃描即可

除了 垂直線 x = k 的特殊情況外
(m, c) 對於線的表示（不是線段）是唯一的

在 x = k 的情況下，可作以下處理

m ← INFINITY
c ← k

時間複雜度同樣是 O(N lg N)

---

總結 - Equation VS Vector：

解2 (equation) 的 好處在於 code length 較短
而弊處在於要額外處理垂直線

而應用了 vector 的 解1 則免卻這麻煩
（本人的經驗是，很多時候 vector 就是好在這個地方）

不過 vector 的運算中... 要寫比較多的（雖然大多是 one-liner） method
（如 rotate, normalize, dot product, cross product...）
相對之下，這題如果應用 x-y equation 可以減省許多 code length

所以嘛... 有時候，決定該用 equation 還是 vector 也頗重要