在1964年的洪水侵襲札格拉布(Zagreb)這座城市後造成了許多的災難。許多的建築物在洪水襲擊牆壁後被完全地摧毀。在本題中，給定一個這個城市在洪水侵襲前的簡化模型，請找出哪些牆壁在洪水侵襲之後將仍然保持完整無缺。
這個模型包括了N個在座標平面上的點與W個牆壁，其中每一個牆壁連接兩個點並且中間不會通過任何其它的點。這個模型有下列的特性:
Ø 兩個牆壁不會相交或是重疊，但他們可能在端點處相接。
Ø 每一個牆壁都是與水平軸平行或是與垂直軸平行。
在剛開始時，整個座標平面是乾的。在時間0時，洪水瞬間地淹沒最外圍(沒有牆壁包圍的空間)。在正好一個小時後，每個牆壁若有一側是水而另一側是空氣的話，就會因水壓的關係而毀壞，洪水然後會淹沒任何沒有被牆壁完整包圍的新區域。這時，將又會有新的牆壁一側是水而另一側是空氣，再經過另一個小時後，這些牆壁也會毀壞而洪水繼續氾濫。這個過程將持續直到洪水淹沒整個區域為止。
下圖是整個過程的一個例子。
寫一個程式，當給定N個點的座標與連接這些點的W個牆壁的描述後，找出哪些牆壁可在洪水侵襲之後依然可以保持挺立。
輸入的第一行有一個整數N (2 ≤ N ≤ 100 000)，代表在平面上點的數目。
接下來N行的每一行都有兩個整數X和Y(兩者都介於0和1,000,000間，包括0與1,000,000)，表示每一點的座標值。這些點將依照它們被給定的順序編號1到N。沒有任何兩點會座落在相同座標。
接下來的一行有一個整數W (1 ≤ W ≤ 2N)，是表示牆壁的數目。
接下來W行的每一行都有兩個不同的整數A和B (1 ≤ W ≤ 2N)，表示在洪水來犯前有一個牆壁連接A與B兩點。這些牆壁將依照它們被給定的順序編號1到W。輸出的第一行應該有一個整數K，代表在洪水過後仍然保持挺立牆壁的數目。
接下來的K行應該列出那些還依然挺立牆壁的編號，每行一個牆壁。這些牆壁可以以任何順序輸出。
※為了judge方便，請將編號由小到大輸出
15 1 1 8 1 4 2 7 2 2 3 4 3 6 3 2 5 4 5 6 5 4 6 7 6 1 8 4 8 8 8 17 1 2 2 15 15 14 14 13 13 1 14 11 11 12 12 4 4 3 3 6 6 5 5 8 8 9 9 11 9 10 10 7 7 6
4 6 15 16 17
公開 測資點#0 (5%): 2.0s , <10M
公開 測資點#1 (5%): 2.0s , <10M
公開 測資點#2 (5%): 2.0s , <10M
公開 測資點#3 (5%): 2.0s , <10M
公開 測資點#4 (5%): 2.0s , <10M
公開 測資點#5 (5%): 2.0s , <10M
公開 測資點#6 (5%): 2.0s , <10M
公開 測資點#7 (5%): 2.0s , <1M
公開 測資點#8 (5%): 2.0s , <1M
公開 測資點#9 (5%): 2.0s , <1M
公開 測資點#10 (5%): 2.0s , <1M
公開 測資點#11 (5%): 2.0s , <1M
公開 測資點#12 (5%): 2.0s , <1M
公開 測資點#13 (5%): 2.0s , <1M
公開 測資點#14 (5%): 2.0s , <1M
公開 測資點#15 (5%): 2.0s , <1M
公開 測資點#16 (5%): 2.0s , <1M
公開 測資點#17 (5%): 2.0s , <1M
公開 測資點#18 (5%): 2.0s , <1K
公開 測資點#19 (5%): 2.0s , <1K
佔總分40分的測試資料中，每組所有點的座標值最大將會是500。
上述的測試資料及另外15分的測試資料其點的數目最多將會是500。| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||