a566: IOI2007 Day1.2.洪水問題
Tags :
Accepted rate : 11人/13人 ( 85% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 02:05

Content

    1964年的洪水侵襲札格拉布(Zagreb)這座城市後造成了許多的災難。許多的建築物在洪水襲擊牆壁後被完全地摧毀。在本題中,給定一個這個城市在洪水侵襲前的簡化模型,請找出哪些牆壁在洪水侵襲之後將仍然保持完整無缺。

    這個模型包括了N個在座標平面上的點與W個牆壁,其中每一個牆壁連接兩個點並且中間不會通過任何其它的點。這個模型有下列的特性:

Ø  兩個牆壁不會相交或是重疊,但他們可能在端點處相接。

Ø  每一個牆壁都是與水平軸平行或是與垂直軸平行。

 

    在剛開始時,整個座標平面是乾的。在時間0時,洪水瞬間地淹沒最外圍(沒有牆壁包圍的空間)。在正好一個小時後,每個牆壁若有一側是水而另一側是空氣的話,就會因水壓的關係而毀壞,洪水然後會淹沒任何沒有被牆壁完整包圍的新區域。這時,將又會有新的牆壁一側是水而另一側是空氣,再經過另一個小時後,這些牆壁也會毀壞而洪水繼續氾濫。這個過程將持續直到洪水淹沒整個區域為止。

 

下圖是整個過程的一個例子。

 寫一個程式,當給定N個點的座標與連接這些點的W個牆壁的描述後,找出哪些牆壁可在洪水侵襲之後依然可以保持挺立。

Input

    輸入的第一行有一個整數N (2 ≤ N ≤ 100 000),代表在平面上點的數目。

    接下來N行的每一行都有兩個整數XY(兩者都介於01,000,000間,包括01,000,000),表示每一點的座標值。這些點將依照它們被給定的順序編號1N。沒有任何兩點會座落在相同座標。

    接下來的一行有一個整數W (1 ≤ W ≤ 2N),是表示牆壁的數目。

    接下來W行的每一行都有兩個不同的整數AB (1 ≤ W ≤ 2N),表示在洪水來犯前有一個牆壁連接AB兩點。這些牆壁將依照它們被給定的順序編號1W
Output

   輸出的第一行應該有一個整數K,代表在洪水過後仍然保持挺立牆壁的數目。

    接下來的K行應該列出那些還依然挺立牆壁的編號,每行一個牆壁。這些牆壁可以以任何順序輸出。

※為了judge方便,請將編號由小到大輸出 

Sample Input
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
Sample Output
4
6
15
16
17
測資資訊:
記憶體限制: 512 MB
公開 測資點#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
Hint :

佔總分40分的測試資料中,每組所有點的座標值最大將會是500

上述的測試資料及另外15分的測試資料其點的數目最多將會是500
Tags:
出處:
IOI2007Day1第二題 [管理者:
david942j (文旋)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」