在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行應該列出那些還依然挺立牆壁的編號,每行一個牆壁。
牆壁請依照編號由小到大輸出!!
注意:
牆壁輸出順序與原先比賽時稍有不同, 請注意
(原先是任意順序)
Notice:
the order in which standing walls should be output is differenet from that of during the contest.
though originally in contest the output order of the walls can be arbitrary,
here for convenience we demand that the output walls must be ordered from small to large.
please be sure to note this change of requirement.
2008.08.02 kelvin
原TIOJ1342 / IOI 2007, Day 1 problemsetter: kelvin
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 4 |
2 | 1 | 4 |
3 | 2 | 4 |
4 | 3 | 4 |
5 | 4 | 4 |
6 | 5 | 4 |
7 | 6 | 4 |
8 | 7 | 4 |
9 | 8 | 4 |
10 | 9 | 4 |
11 | 10 | 4 |
12 | 11 | 4 |
13 | 12 | 4 |
14 | 13 | 4 |
15 | 14 | 4 |
16 | 15 | 4 |
17 | 16 | 4 |
18 | 17 | 4 |
19 | 18 | 4 |
20 | 19 | 4 |
21 | 20 | 4 |
22 | 21 | 16 |