TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

81.8% (18/22)

Submission's AC Ratio

25.6% (23/90)

Tags

Description

台北禮品公司聘請多位藝術家手繪各種俱備美感的吊飾,一旦某個設計經過市場調查確定量產時,就需要進行開模作業。
開模作業已經自動化。首先機器手臂A會將吊飾輪廓先描繪至壓克力片上,描繪的輪廓實際上就是一個多邊形(如圖一(a)所示)。
接下來機器手臂B就會依該多邊形輪廓畫出最小涵蓋整個輪廓的凸多邊形(如圖一(b)所示)。
裁剪機C就會依照該凸多邊形圖案自動裁剪出該凸多邊形的壓克力塊(如圖一(c)所示)。
接下來機器手臂D就會將凸多邊形與實際圖案輪廓之間的多餘區塊均勻上色。
最後裁剪機D就會自動的把有上色的區塊裁掉,剩下最後的吊飾半成品(如圖一(D)所示)。
這整個作業流程中唯有第三步驟會有耗材的損耗,即上色用的色塊。
每一個色塊能夠用來塗滿的區域面積是固定的。
因此每一次開模作業所需用掉的色塊數會依圖案實際需求而有所不同。
給定一個已裁剪出的凸多邊形壓克力塊、需要開模的多邊形圖案(即圖一(b)中的多邊形),
以及每一個色塊可塗滿的面積資訊,請計算出所需的色塊數量。

條件限制
(1) 多邊形最少有四個邊,最多有20個邊,亦即最多有20個角。每一個角的平面座標皆符合0 <= x, y <= 10,000。
(2) 色塊能夠塗滿的區域面積最多為1,000平方公分。

Input Format

輸入檔第一行有兩個數字:
n, a,分別代表多邊形的邊數及色塊能夠塗滿的面積(平方公分)。
接下來的n 行每行有兩個數字:
x, y,代表多邊形上的一個角的座標;以第一個角為基準依逆時鐘方向依序列出。

Output Format

請輸出一個整數,即塗滿必須去除的區域所需用到的總色塊數。

Sample Input 1

4 10
0 0
5 5
10 0
5 10

Sample Output 1

3

Sample Input 2

5 1000
1 10
2 1
12 1
14 5
7 12

Sample Output 2

0

Hints

Problem Source

原TIOJ1678 / 98北市賽(prob 2)

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5