有些問題很難解,卻可以簡化成簡單的題目,例如解本問題時不必真的建構出一個複雜的地球模型,而只須利用前哥倫布時期的地平說觀念,建立一個長 500 公里、寬 500 公里的正方形平面。
本問題所研究的平面世界中有許多國家正在打仗,這個世界的人民雖然很好戰,同時卻又是絕對的孤立主義者,每個國家都用一堵高高的圍牆 (同時又很薄) 把國境圍起來,用來保護自已的國家並且與其他國家隔離,為了避免能源戰爭,每個國家都有自已的發電廠。
當戰事愈演愈烈、一發不可收拾的時候,他們發射飛彈攻擊其他國家,「SCUD 汎用型淨化破壞兵器 (Sanitary Cleansing Universal Destroyer)」瞄準敵國境內的發電廠,在不傷及性命的情況下癱瘓敵國的運作。
給定一個國家的位置座標 (以國境內建築物與發電場所在位置來表示),以及飛彈瞄準的地點,你必須寫一個程式計算當各國的飛彈摧毀發電廠之後,所有國家陷入停電狀態的總面積為何。
國與國之間互不重疊,另外,各國邊境上的高牆厚度可略忽不計。圍住一國國境的高牆為國家的最短周長 (the minimal-perimeter wall),緊緊圍繞在國內所有建築物與發電廠的周圍,一個國家的面積為高牆所圍往的面積。
每個國家都只有唯一一座發電廠。
國與國之間可能會有不屬於任一國家的空間。
Input
輸入資料為各國國內所有建築物的位置資訊,緊接著一連串飛彈的攻擊位置。
一國家的位置、面積資訊首先包含一整數 N ($3\leq{N}\leq{100}$),用來表示國內所有建築物數量。下一列表示發電廠位置的 (x, y) 座標,再接下來的 N-1 列為國內其他建築物位置的 (x, y) 座標。電廠供所有建築物用電。當 N 等於 -1 時表示沒有其他國家,輸入資料最少有一個國家。
國家資訊輸入完畢後,再接下來會指示飛彈攻擊的地點,會有一到多個飛彈被發射。每顆飛彈的攻擊位置一列,直到檔案結尾。
位置資訊是以公里為單位,構成 500 * 500 的方格,每一點座標皆為 0 到 500 的整數,以一對以空白隔開的整數表示。輸入資料最多會有 20 個國家,而飛彈的數量則不限。
Output
輸出只有一個數值,用來表示所有飛彈發射之後所有國家的停電面積,數值顯示 (且精確) 到小數點下兩位。
Sample Input
12
3 3
4 6
4 11
4 8
10 6
5 7
6 6
6 3
7 9
10 4
10 9
1 7
5
20 20
20 40
40 20
40 40
30 30
3
10 10
21 10
21 13
-1
5 5
20 12
Sample Output
70.50
Hint
下列公式也許會有用。
給定一多邊形的所有頂點 $v_{0}, v_{1},\cdots{}, v_{n}$,且 $v_{0} = v_{n}$,多邊形所圍住的面積公式如下:
$a = \frac{1}{2} \sum_{i = 1}^{n} (x_{i-1} y_{i}) - (x_{i}y_{i-1})$各頂點位置以 x、y 表示為 $v_{i} = (x_{i}, y_{i})$ 多邊形的邊定義為頂點 $v_{i}$ 到頂點 $v_{i+1}$, for $i=0\cdots{n-1}$ .
當多邊形的頂點依序以逆時針方向表示時,面積 a 為正值,反之,當頂點以順時針方向依序列出時,面積 a 為負值。