在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
佔總分40分的測試資料中,每組所有點的座標值最大將會是500。
上述的測試資料及另外15分的測試資料其點的數目最多將會是500。編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|