2013-02-21 08:33:29Morris
[ZJ][多邊形面積] d546. 3. 剪多邊形（molding）
內容 ：
台北禮品公司聘請多位藝術家手繪各種俱備美感的吊飾，一旦某個設計經過市場調查確定量產時，就需要進行開模作業。開模作業已經自動化。
- 首先機器手臂Ａ會將吊飾輪廓先描繪至壓克力片上，描繪的輪廓實際上就是一個多邊形（如圖(a)所示）
- 接下來機器手臂Ｂ就會依該多邊形輪廓畫出最小涵蓋整個輪廓的凸多邊形（如圖(b)所示）
- 裁剪機Ｃ就會依照該凸多邊形圖案自動裁剪出該凸多邊形的壓克力塊（如圖(c)所示）
- 接下來機器手臂Ｄ就會將凸多邊形與實際圖案輪廓之間的多餘區塊均勻上色
- 最後裁剪機Ｄ就會自動的把有上色的區塊裁掉，剩下最後的吊飾半成品（如圖(d)所示）
這整個作業流程中唯有第三步驟會有耗材的損耗，即上色用的色塊。每一個色塊能夠用來塗滿的區域面積是固定的，因此每一次開模作業所需用掉的色塊數會依圖案實際需求而有所不同。
給定一個已裁剪出的凸多邊形壓克力塊、需要開模的多邊形圖案（即圖(b)中的多邊形），以及每一個色塊可塗滿的面積資訊，請計算出所需的色塊數量。
(a) (b) (c) (d) (e)
多邊形最少有四個邊，最多有 20 個邊，亦即最多有 20 個角
每一個角的平面座標皆符合 0 <= x, y <= 10000
色塊能夠塗滿的區域面積最多為 1000 平方公分
輸入說明
：
輸入檔第一行有兩個數字 n, a 分別代表多邊形的邊數及色塊能夠塗滿的面積（平方公分）
接下來的 n 行每行有兩個數字 x, y 代表多邊形上的一個角的座標 以第一個角為基準依逆時鐘方向依序列出。
輸出說明
：
請輸出一個整數，即塗滿必須去除的區域所需用到的總色塊數
範例輸入 ：
4 10 0 0 5 5 10 0 5 10
範例輸出 ：
3
提示
：
出處
：
北市 98 資訊學科能力競賽
(管理：example)
這題跟 UVa 10065 差不多。
剛開始以為每次塗的時候色塊都要相連，但是實際上題目應該是要問塗的次數，
一次最多上色那麼多面積，問至少要幾次才能塗完。
問色塊數反而讓我混淆了，以為一定要相連，想起來寫就麻煩了。
#include <stdio.h>這題跟 UVa 10065 差不多。
剛開始以為每次塗的時候色塊都要相連，但是實際上題目應該是要問塗的次數，
一次最多上色那麼多面積，問至少要幾次才能塗完。
問色塊數反而讓我混淆了，以為一定要相連，想起來寫就麻煩了。
#include <algorithm>
#include <math.h>
using namespace std;
struct Pt {
double x, y;
};
Pt P[2000], CH[2000];
double calc_area(Pt P[], int n) {
double ans = 0;
int i;
for(i = 0; i < n; i++)
ans += P[i].x*P[i+1].y - P[i].y*P[i+1].x;
return fabs(ans)/2;
}
double cross(Pt o, Pt a, Pt b) {
return (a.x-o.x)*(b.y-o.y)-
(a.y-o.y)*(b.x-o.x);
}
bool cmp(Pt a, Pt b) {
if(a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
int monotone(int n) {
sort(P, P+n, cmp);
int i, m, t;
m = 0;
for(i = 0; i < n; i++) {
while(m >= 2 && cross(CH[m-2], CH[m-1], P[i]) <= 0)
m--;
CH[m++] = P[i];
}
for(i = n-1, t = m+1; i >= 0; i--) {
while(m >= t && cross(CH[m-2], CH[m-1], P[i]) <= 0)
m--;
CH[m++] = P[i];
}
return m;
}
int main() {
int n, cases = 0, i;
double p;
while(scanf("%d %lf", &n, &p) == 2) {
for(i = 0; i < n; i++)
scanf("%lf %lf", &P[i].x, &P[i].y);
P[n] = P[0];
double tile = calc_area(P, n);
int m = monotone(n);
double cont = calc_area(CH, m-1);
printf("%d\n", (int)ceil((cont-tile)/p));
}
return 0;
}