d546: 3. 剪多邊形(molding)
Tags :
Accepted rate : 57人/60人 ( 95% ) [非即時]
評分方式:
Tolerant

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

Content

 台北禮品公司聘請多位藝術家手繪各種俱備美感的吊飾,一旦某個設計經過市場調查確定量產時,就需要進行開模作業。開模作業已經自動化。

  1. 首先機器手臂A會將吊飾輪廓先描繪至壓克力片上,描繪的輪廓實際上就是一個多邊形(如圖(a)所示)
  2. 接下來機器手臂B就會依該多邊形輪廓畫出最小涵蓋整個輪廓的凸多邊形(如圖(b)所示)
  3. 裁剪機C就會依照該凸多邊形圖案自動裁剪出該凸多邊形的壓克力塊(如圖(c)所示)
  4. 接下來機器手臂D就會將凸多邊形與實際圖案輪廓之間的多餘區塊均勻上色
  5. 最後裁剪機D就會自動的把有上色的區塊裁掉,剩下最後的吊飾半成品(如圖(d)所示)

這整個作業流程中唯有第三步驟會有耗材的損耗,即上色用的色塊。每一個色塊能夠用來塗滿的區域面積是固定的,因此每一次開模作業所需用掉的色塊數會依圖案實際需求而有所不同。

給定一個已裁剪出的凸多邊形壓克力塊、需要開模的多邊形圖案(即圖(b)中的多邊形),以及每一個色塊可塗滿的面積資訊,請計算出所需的色塊數量。

     (a)                (b)            (c)             (d)              (e)
 

 多邊形最少有四個邊,最多有 20 個邊,亦即最多有 20 個角

 每一個角的平面座標皆符合 0 <= x, y <= 10000

 色塊能夠塗滿的區域面積最多為 1000 平方公分

Input

 輸入檔第一行有兩個數字  n, a 分別代表多邊形的邊數及色塊能夠塗滿的面積(平方公分)

 接下來的 n 行每行有兩個數字 x, y 代表多邊形上的一個角的座標 以第一個角為基準依逆時鐘方向依序列出。

Output
 請輸出一個整數,即塗滿必須去除的區域所需用到的總色塊數
Sample Input
4 10
0 0
5 5
10 0
5 10
Sample Output
3
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (50%): 5.0s , <1K
公開 測資點#1 (50%): 5.0s , <1K
Hint :
Tags:
出處:
98學年度台北市資訊學科能力競賽 [管理者:
example (學姊)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」