Ruby兔的ACM園地: 109

SCUD汎用型淨化破壞兵器

Background

有些問題很難解，卻可以簡化成簡單的題目，例如解本問題時不必真的建構出一個複雜的地球模型，而只須利用前哥倫布時期的地平說觀念，建位一個長500公里、寬500公里的正方形平面。

本問題所研究的平面世界中有許多國家正在打仗，這個世界的人民雖然很好戰，同時卻又是絕對的孤立主義者，每個國家都用一堵高高的圍牆(同時又很薄)把國境圍起來，用來保護自已的國家並且與其他國家隔離，為了避免能源戰爭，每個國家都有自已的發電廠。

當戰事愈演愈烈、一發不可收拾的時候，他們發射飛彈攻擊其他國家，「SCUD汎用型淨化破壞兵器((Sanitary Cleansing Universal Destroyer)」瞄準敵國境內的發電廠，在不傷及性命的情況下癱瘓敵國的運作。

給定一個國家的位置座標(以國境內建築物與發電場所在位置來表示)，以及飛彈瞄準的地點，你必須寫一個程式計算當各國的飛彈催毀發電廠之後，所有國家陷入停電狀態的總面積為何。

國與國之間互不重疊，另外，各國邊境上的高牆厚度可略忽不計。圍住一國國境的高牆為國家的最短周長(the minimal-perimeter wall)，緊緊圍繞在國內所有建築物與發電廠的周圍，一個國家的面積為高牆所圍往的面積。

每個國家都只有唯一一座發電廠。

國與國之間可能會有不屬於任一國家的空間。

輸入資料為各國國內所有建築物的位置資訊，緊接著一連串飛彈的攻擊位置。

一國家的位置、面積資訊首先包含一整數 N ( ) ，用來表示國內所有建築物數量。下一列表示發電廠位置的(x, y)座標，再接下來的N-1列為國內其他建築物位置的(x, y)座標。電廠供所有建築物用電。當N等於 -1 時表示沒有其他國家，輸入資料最少有一個國家。

國家資訊輸入完畢後，再接下來會指示飛彈攻擊的地點，會有一到多個飛彈被發射。每顆飛彈的攻擊位置一列，直到檔案結尾。

位置資訊是以公里為單位，構成500*500的方格，每一點座標皆為0到500的整數，以一對以空白隔開的整數表示。輸入資料最多會有20個國家，而飛彈的數量則不限。

輸出只有一個數值，用來表示所有飛彈發射之後所有國家的停電面積，數值顯示(且精確)到小數點下兩位。

70.50

下列公式也許會有用。

給定一多邊形的所有頂點，且，多邊形所圍住的面積公式如下：

各頂點位置以x, y表示為，多邊形的邊定義為頂點到頂點 , for .

當多邊形的頂點依序以逆時針方向表示時，面積a為正值，反之，當頂點以順時針方向依序列出時，面積a為負值。