98全國賽 園藝達人的除草計畫

題目：

給定一個以水平線段和垂直線段組成的封閉草坪，現在要將草坪分割，

方式是依草坪邊界的水平線作延伸，而將整個草坪切割成數個小方塊，

再將切割出來的小草坪依照其左下角頂點的座標以低至高以及左至右來作排序，

題目要求必須找出所有的小方塊，並且依照格式做輸出，

輸入的格式是給此封閉區塊的所有頂點(<=500)，詳細的題目可以參考 ZeroJudge。

解法：

我對這個題目的核心思想是 D&C，

首先觀察到的第一個性質是：

一條垂直的邊 L1 往左右掃到的第一個垂直邊 L2 時，一定會形成方塊，

於是，不需考慮水平線，只存垂直邊即可，

垂直線照 X軸 排序後，開始由每一條邊往右掃，

可以觀察出，L1、L2的分割情形有四種：

於是，將 L1、L2 的重疊區域扣掉分成兩小段，並且會得到一個新的矩形，

其餘則切割成兩小段遞迴處理！

必須要注意的一點是，並不是每一條線掃的時候都是往右，

可以發現，當 L1 向右掃到 L2 時，

切割後的線段若屬於 L1，則此線段掃的方向向右，

切割後的線段若屬於 L2，則此線段掃的方向往左，

證明並不困難，畫畫看就知道了，

並且一開始進入遞迴時，方向一定是向右的，

因為如果向左可以找到一個小方塊，

之前的線段必定已掃過，故不存在往左掃的線段。

由於每個小方塊只被算過一遍，最差情況下每條線段兩兩要互相檢查，

複雜度應是O(N^2)，點的數量只有 500 個，

最差情況的測資也不好構造，應該可以輕鬆跑出結果。

AC (4ms, 274KB)