a512: 陳師傅的專業技能
標籤 : 112彰雲嘉資訊學科
通過比率 : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-10-15 15:48

內容

有一位技能高超的貼磁磚陳師傅,他常常接一些別人眼中無法獲利的工程,原因是這些工程在貼磁磚上有一些限制,別的師傅都是先把磁磚貼上,再打掉不完整的磁磚,導致浪費很多磁磚,而陳師傅只貼上必要完整的磁磚,所以節省很多不必要的浪費,這些貼磁磚的規則如下敘述:
在要貼磁磚的平面區塊上,依序標示一個具有整數座標的封閉多邊形,找出被多邊形完全涵蓋包圍的白色和灰色磁磚的數量,而沒有完整涵蓋到的磁磚,必須去除而不予計算;
灰色和白色磁磚間格著貼,類似棋盤(如圖所示,白色磁磚旁邊是灰色磁磚),座標(0,0)‐(0,1)‐(1,1)‐(1,0)區塊貼白色磁磚,並以此向四周白灰相間。
舉例說明: 如圖在棋盤磁磚上依序標示一個具有整數座標的封閉多邊形頂點,(2,1), (8,3), (11,2),(6,8),則在此封閉區間內,包含6 個完整的灰色磁磚和5 個完整的白色磁磚。原點座標(0,0)在左下角。

輸入說明

每組測資將由兩列組成,可連續測試多組測資,直到沒有測資就結束運算。
每組測資的第一列為此多邊形區域的頂點數N (3 =<  N =< 10000),

接著依序有N 列頂點平面座標(x, y), (0 =< x =< 0000, 0 =<  y =<  10000, x, y 為整數)。

若還有測資,則按規則依序列出。

 

輸出說明

每一測資輸出一列,被封閉多邊形完全涵蓋包圍的灰色及白色磁磚的數量(磁磚數目皆為整數),由小到大列出完整的灰色磁磚數目和完整的白色磁磚數目(先白再灰,或先灰再白,依數字由小到大排列,若數字一樣,則先白再灰,或先灰再白皆可)。

範例輸入 #1
4
2 1
8 3
11 2
6 8
範例輸出 #1
5 6
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (100%): 1.0s , <1K
提示 :
標籤:
112彰雲嘉資訊學科
出處:
112彰雲嘉資訊學科 [管理者: ]


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