d600: 5.景觀餐廳
標籤 :
通過比率 : 29人/35人 ( 83% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-09-14 11:53

內容

     蓋茲是個十分富有的商人,他最近剛買下台北市近郊的一塊土地,並且打算
在將來退休後,從事務農的生活。但是,在買下這塊土地後,蓋茲才發現另一件
事實,就是這塊地的某些部份,其實在二十年前是一間化學工廠的舊址,由於這
家化學工廠專門生產有毒物質,因此依照法律規定,這家工廠的廠址在一百年內
都不可以用來從事農業活動。聰明的蓋茲想到一個好的解決方法,就是將他所擁
有的土地分成兩種用途使用:一部份是原先化學工廠的舊廠址區,用來經營景觀
餐廳;剩下來的區域,則用來從事農業活動。
    舉例來說,若蓋茲所購買的土地為一個四邊形,其端點座標依序為(1,1), (7,1),
(7,7), (1,7),且化學工廠的舊址為一個三角形區域,其端點座標依序為(4,2), (10,2),
(7,6),則我們可以從下圖中得知蓋茲的景觀餐廳座落於以(7,6), (4,2), (7,2)為端點
的三角形區域內,且其面積為6.00。

為方便起見,我們假設蓋茲所擁有的土地,和這家化學工廠的廠址皆是一個
凸多邊形區域(且兩個多邊形存在互相重疊的區域),請您幫忙計算蓋茲未來用
來經營景觀餐廳的土地面積。

輸入說明
    第一行輸入一個正整數M,代表蓋茲所購買的土地可以用M 邊形表示。接
下來的M行中,每一行有兩個以一個空白符號相間隔的整數,分別為x和y。
接下來的一行輸入一個正整數N,代表這家化學工廠的原廠址可以用N 邊形
表示。接下來的N 行中,每一行有兩個以一個空白符號相間隔的整數,分別為x
和y。
    為簡化起見,所有的測試資料皆滿足3 ≤ M≤ 20,3≤ N ≤ 20,0 ≤x ≤ 100,
且0 ≤ y ≤ 100。同時,描述蓋茲所購買的土地的M多邊形的M個點,以及化學
工廠原廠址的N 多邊形的N 個點,皆是依照逆時針的方向依次輸入。化學工廠
的舊址可能完全包含於蓋茲的土地上,也可能只有一部份包含於蓋茲的土地上。
輸出說明
    根據輸入的土地資料,輸出蓋茲未來用來經營景觀餐廳的土地面積(四捨五
入到小數點下第二位)
範例輸入
輸入範例1:
4
1 1
7 1
7 7
1 7
3
4 2
10 2
7 6

輸入範例2:
4
1 1
7 1
14
7 7
1 7
3
1 2
7 2
4 6
範例輸出
輸出範例1:
6.00

輸出範例 2:
12.00
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 2.0s , <1K
公開 測資點#1 (20%): 2.0s , <1K
公開 測資點#2 (20%): 2.0s , <1K
公開 測資點#3 (20%): 2.0s , <1K
公開 測資點#4 (20%): 2.0s , <1K
提示 :

    對用( x0 , y0 ), ( x1 , y1 ), …, ( xn-1 , yn-1 )(按逆時針排列)描述的多邊形,若令
xn=x0且yn=y0,其面積為:

 

感谢morris1028!

標籤:
出處:
98學年度全國資訊學科能力競賽 [管理者:
swda289346 (太威啦)
]


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