PKU3168-Barn Expansion

題目：http://poj.org/problem?id=3168
給出N(25000)個不重疊的矩形，惟矩形之間可能共邊或共點
所謂可擴張矩形，是那些「不和任何其他矩形共邊或共點」的矩形
問這樣的可擴張矩形有幾個？


程式碼：(codepad掛了，待補)

充分利用「矩形不重疊」的特性：多想兩分鐘，你可以不用開線段樹掃描

一開始想利用map來解決，竟然TLE了，
本以為是我沒設定好sort之類的、自己抓測資來測才發現在我本機最大要跑700ms
後來不用map的輕鬆作法就應運而生了：

把每一個矩形，通通拆成四條邊來看待
發現只要把「x座標一樣、y1y2線段重疊」類以及y-x1x2類拿出來檢查，
就是所有可能共邊的情況
主架構就是先依x為主(鉛錘線段)排序，x相同者依y1排序
然後掃一遍區分出x相同的「叢」，送去作線段覆蓋檢查
再來同樣的方法處理依y為主(水平線段)的邊

至於如何檢查線段間是否有互相覆蓋？這可以利用經典的貪心模型來解決
方便描述這裡線段的起點稱p、終點稱q
先看看這道式子，如果兩線段[p1,q1][p2,q2]「沒有覆蓋」的充要條件就是：
　　p1>q2 || q1<p2 ...(1)
　　線1在線2的右邊 或 線1在線2左邊

如果具有p1<=p2(線段[p1,q1]相對左邊)，那麼有覆蓋的充要條件就是：
　　p2<=q1 ...(2)

(參考程式碼的check函式)
大約是這樣的：想像「一坨」交疊的線段[p,q]，以及「一條」待檢察的線段line[j]
想知道line[j]是否和前面的任何一條線段有所交疊，其實不必一條一條檢察
只要在掃過來的過程(i+1...j-1)不斷更新聯集、擴大假想線段[p,q]
檢查line[j]是否和[p,q]交疊即可

前面說過，線段已經排序過了(也就是按照起點p排序)
就是說line[j]永遠都在[p,q]的右邊，參考式(2)就是[p,q]當線段1、line[j]當線段2
如果發生交疊，就說明line[j]在這段交疊群裡、那麼就更新擴大[p,q]
反之沒有交疊的話就另起爐灶，並且順便判斷最開頭的line[i]是不是獨立線段
(交疊群只有line[i]一條，是為獨立)

到這裡就解出來了

當然、也可以想像成括號匹配什麼的，畢竟能貪心的題目總是那麼「多心」