USACO Section 3.1 Shaping Regions

題目：

N個不同顏色的不透明長方形(N<=1000)放在一個長為A，寬為B(<=10000)的白紙上。

這些長方形放置時保證邊與白紙的邊平行，所有的長方形都會在白紙內。

給定放置的順序及長方形的邊長與顏色(<=2500)，求出各顏色所占的面積。


解法：

這題是被雷之後寫出來的，方法貌似很多種，

我用的解法是 D&C，核心概念就是把大問題拆成小問題。

首先可以知道，最後覆蓋上去的長方形一定不會被之前的所遮蓋，

於是可以利用這個特性，先由最後放上去的開始處理，

將中央的長方形處理完後，原來的圖形可以被切割成四塊(Divide)，

由於 A B C D 中任一矩形都不會再被中央長方形覆蓋，

故之後處理時可以從中央矩形的上一個開始，

如此繼續操作下去，即可得到各色區的面積。

用這樣的解法跑測資最後一筆是0.011s。