d599. 4. 園藝達人的除草計畫 - 高中生程式解題系統

內容

有位自行創業的園藝達人專長是幫客戶整理草坪，客戶草坪的邊界必須是
水平線以及垂直線，不可以是斜線，為了便於有系統的整理各種形狀的草坪，這
位園藝達人發展出一套有效率的草坪分區管理機制，方式是依草坪邊界的水平線
作延伸而將整個草坪切割成數個方塊(長方或正方形)，然後再將切割出來的小草
坪依照其左下角頂點的座標以低至高以及左至右的順序來作排序，然後每日依此
排列順序固定整理幾塊小草坪，依序整理完整塊大草坪，這樣就不會有遺漏以及
有些地區的草太長的問題。在切割草坪時，園藝達人先沿著草坪邊界依逆時針方
向行走，並且記錄每條線的方向，如圖一(a)與圖二(a)，他的原始想法是先將兩
條垂直線投影到y座標上，如果兩條垂直線在y座標上的投影有重疊即可產生一
塊小草坪，例如圖二的垂直線e1與e2在y座標上的投影有30單位的重疊線段(圖
二(b)的垂直長線段與垂直短線段分別顯示e1 與e2 在y 座標上的投影)，因此可
以產生一高30 單位的小草坪，後來發現此想法有錯，例如垂直線e1 與e3 雖然
在y座標上的投影有20 個單位的重疊線段，但卻不能產生一個小草坪，同樣地，
e1 與e4 也有20 個單位的重疊線段，也不能產生一個小草坪，請幫園藝達人改
進其想法，寫出一個園藝草坪切割程式。圖一(b)與圖二(b)為正確的切割結果。

輸入說明

檔案第一行描述草坪邊界共有幾個頂點，第二行開始每一行描述一個頂點，x座
標先y座標隨後，兩個座標中間以一空白(space)隔開。第一個頂點可以是任何一
個頂點，頂點的順序為逆時鐘方向，頂點的個數不會超過500 個頂點，頂點座標
值是介於(包含)0 到10000 的整數。在頂點描述完畢後開始描述輸出的要求。緊
接著頂點描述後的第一行是兩個整數(中間由一個空白隔開)，第一個整數描述共
有幾個小草坪子集合，第二個整數描述每一個子集合中有幾個小草坪，接著就是
依序在一行中描述一個子集合內所包含的小草坪的編號，子集合中相鄰小草坪編
號由一個空白隔開。小草坪編號產生如下。請先將所有切割出來的小草坪依照其
左下角頂點的座標以低至高為第一優先然後由左至右為第二優先的順序來作排
序，排列順序第一個小草坪編號為1，其後每個小草坪的編號依排列順序循序加
1。以輸入範例1 為例，(0,10)為頂點的最後一點，下一行為兩整數3 與3，表示
後面有三個小草坪子集合，每一個小草坪子集合包含3 個小草坪，第一個小草坪
子集合包含編號1，2，3 的小草坪，第二個小草坪子集合包含編號1，2，5 的小
草坪，第三個小草坪子集合包含編號2，4，5 的小草坪。

輸出說明

第一行輸出共有幾個小草坪，第二行輸出所有奇數編號小草坪的面積總和，然後
先算出平均面積(總面積/小草坪總數，以浮點數儲存)，第三行將單一面積比平均
面積大或者相等的小草坪的面積加總後輸出，第四行以後依序輸出在輸入檔案中
指定的小草坪子集合裡所有小草坪的面積總合。以輸出範例1 為例，第一行輸出
總共有5 個小草坪，第二行輸出奇數編號的小草坪面積總和為1250。由於平均
面積為400(2000/5=400)，共有編號1，3，4 號小草坪面積大於或等於400(分別
為450，500 與400)，因此第三行輸出1350。輸入檔案的第一個子集合編號為1，
2，3，因此將編號 1，2，3 號的小草坪面積相加(450+350+500=1300)而在第四行
輸出1300，同樣地將輸入檔案的第二個子集合編號為1，2，5 號的小草坪面積
相加(450+350+300=1100)而在第五行輸出1100，最後將輸入檔案的第三個子集合
編號為2，4，5 號的小草坪面積相加(350+400+300=1050)而在第五行輸出1050。
只要有一個輸出值為錯該題就算錯誤。

範例輸入 #1

輸入範例1：
假設圖一(a)草坪的起始頂點為(0,0)，輸入檔案的內容如下，注意，起始點與最後
一點兩點相鄰。
12
0 0
45 0
45 20
60 20
60 50
30 50
30 40
20 40
20 30
10 30
10 10
0 10
3 3
1 2 3
1 2 5
2 4 5
輸入範例2：
14
0 0
10 0
10 30
30 30
30 10
60 10
60 30
50 30
50 60
40 60
40 40
20 40
20 50
0 50
3 3
1 3 4
2 3 5
3 4 5

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (20%): 2.0s , <1K
公開測資點#1 (20%): 2.0s , <1K
公開測資點#2 (20%): 2.0s , <1K
公開測資點#3 (20%): 2.0s , <1M
公開測資點#4 (20%): 2.0s , <1M

提示：

感谢morris1028提供图片！

標籤:

出處:

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

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