[Hard 2D Geometry] Ural 1464 Light

• 題目在此 

---

這是前幾天在 Timus OJ 的題目分類，按下 Geometry
隨機選擇的一題... (我喜歡隨機選題...)

讀完題目，感覺是經典題目... 但沒有想法...
細心一看... 原來這題還有另一個 Tag ── Hardest Problem
再一看 Accept Rate... 3%

後來跟 Joe 討論過一下，他一兩天就 AC 了...
但他說未能用 STL 的 set implement，只能徒手寫 Heap

(在 Joe 詳細地講解完算法以後)
於是便試試用 STL implement... 結果成功了 !!
不過代價是筋疲力竭
算法雖然直觀，但在處理 ordering 的過程 (見下) 是無限的 confusion + frustration...
而且，最後還要調 epsilon 才通過... (角度 radian, 1e-10)

---

Problem Statement：

給一個簡單 (Simple) N邊形 (N <= 500000)
在其內部放一個點光源 (Strictly inside)
問，光源照到的面積為何？

---

Inutition：

(Preprocess: 把頂點平移，使得光源位置 = origin)

把所有 vertex 的頂點的角度離散化 - { a₁, a₂, a₃, ... a_m }
對於每兩個相鄰的角度：[a_i, a_i+1]
(也就是一個 angle interval)
確定離 origin 最近的 polygon edge - E

那麼，對於這一格，燈所能照到的面積是一個三角形...
(其中一條邊是 E 的 subset，另外兩條是由 origin 沿 a_i 及 a_i+1 射出的 ray)

最後，把所有 angle interval 的三角形面積取和便是答案..

問：如何找最近的 edge？
解：我們可以沿 [a_i, a_i+1] 的角平分線 (angle bisector) cast 一條 Ray
將所有線段相交... 確定最近的 edge

若果對每個 angle interval 做這個操作
總複雜度便會是 O(N²)
太慢了...

我們得竭盡全力想一個 O(N lg N) 的算法

---

Speed-up：

Observation:
edge 與 origin 由近至遠的 ordering
對於相鄰的 angle interval 而言是一樣的

我們可以一邊遞增 angle
用「某種方法」一邊把 線段's push.... pop..

舉個例子:
線段 A 的 angle interval 是 [30, 50]
線段 B 的 angle interval 是 [40, 60]
線段 C 的 angle interval 是 [60, 180]

我們先把 angle 離散化，遞增 angle，並加入 / 刪除 segment...
當 angle = 30 時，push 線段 A
當 angle = 40 時，push 線段 B
當 angle = 50 時，pop 線段 A
當 angle = 60 時，pop 線段 B、push 線段 C

這樣...
在 [30,40] 時我們會考慮 線段 A
在 [40,50] 時我們會考慮 線段 A、B
在 [50,60] 時我們會考慮 線段 B
在 [60,180] 時我們會考慮 線段 C

嗯... 一邊加入或刪除某些元素，而元素的 ordering 是 preseved 的
我們又想查找最大/最小元素...
──其實這就是 Sweep Line Algorithm 的思想
──是一類很直觀，但寫起來很麻煩的算法...

---

STL：

由於 ordering 不變...
上面提到的「某種方法」，可以由 heap 實踐
具體地說... 若果用 STL 的 set
可以寫一個 comparator，用以比較兩條 segment 哪條離 origin 較近
comparator 的 implementation 是會隨著角度變化而改變的...
不過比較得出的結果是恒常不變的...

那我們能否將簡化一點
寫一個當角度變化但 implementation 不變的 comparator？
答案是否定的

（多邊形例子... 圖片後補...）

Syntax:

struct Lt {

  bool operator() ( const int &x, const int &y ) {

    ....

  }

};

set< int, Lt > S;

S.push(1); // push segment 1

至於細節...

若果沒有圖片附助說明的話

恐怕會愈講愈混亂

現時暫沒時間畫圖... 有時間後補吧

---

Remarks:

時間總複雜度:
O(N lg N)

有一點要非常注意：
就是 less than operator 一定要小心處理 tie-breaking
你要確保 operator 不會出現 == 的情況...
否則... 就會出現類似如下（我試過）的情況：

Code:

// 當運行到某一個 iteration...

printf("%d\n", S.size()); // print out 3
printf("%d\n", S.find(4)!=S.end()); // Double check if segment 4 is in S
S.erase(4); // Remove segment 4
printf("%d\n", S.size()); // print out 0 ?!

Console:
3
1
0