a566. IOI2007 Day1.2.洪水問題
標籤 :
通過比率 : 12人/13人 ( 92% ) [非即時]
評分方式:
Tolerant

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

內容

    在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方便,請將編號由小到大輸出 

範例輸入 #1
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
範例輸出 #1
4
6
15
16
17
測資資訊:
記憶體限制: 512 MB
提示 :

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

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

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」