這個題確實太神奇了
大意就是給出了n個互不相交的圓。 各個圓之間有可能一個完全包含了另一個。這裡包含就是一個圓整個都被另一個圓圈再裡面。
現在求那些沒有被包含的圓的序號。
數據量是4W
所以N2的肯定不行。
苦思冥想，不得其解
看了這個之後不由得大呼數據結構之博大精深
大意就是類似於我們經常用的那種掃描線，只不過這裡是圓。
每個圓有最左邊的點和最右邊的點。我們就是從左到右按順序把這些點掃一遍。
掃的過程中呢，如果掃到了一個圓的左端點，那麼就要看這個圓是否被包含了，如果沒被包含，就加入我們設計的數據結構中。那麼怎麼判斷有沒有被包含了呢，最裸的想法是看是否被之前數據結構中的圓包含。實際上只需要跟數據結構中跟自己圓心縱坐標相近的上下兩個圓來判斷即可了，因為此時我們設計的數據結構中一定都是一些互不包含的一些圓，如果新進的這個圓被包含了，那麼那個包含它的圓必然在其相鄰的地方。
如果掃到了一個圓得右端點呢，就要把這個圓刪除掉了，因為再往後的圓不會跟它發生關系了。
根據這個能插入，能刪除，能找相鄰的條件，可以發現，用set 來實現是再好不過了。
