[UVA][簡單多邊形面積] 10065 - Useless Tile Packers
Problem A
Useless Tile Packers
Input: standard input
Output: standard output
Yes, as you have apprehended the Useless Tile Packers (UTP) pack tiles. The tiles are of uniform thickness and have simple polygonal shape. For each tile a container is custom-built. The floor of the container is a convex polygon and under this constraint it has the minimum possible space inside to hold the tile it is built for. But this strategy leads to wasted space inside the container.
The UTP authorities are interested to know the percentage of wasted space for a given tile.
Input
The input file consists of several data blocks. Each data block describes one tile.
The first line of a data block contains an integer N (3 <= N <= 100) indicating the number of corner points of the tile. Each of the next N lines contains two integers giving the (x, y) co-ordinates of a corner point (determined using a suitable origin and orientation of the axes) where 0 <= x, , y <= 1000. Starting from the first point given in the input the corner points occur in the same order on the boundary of the tile as they appear in the input. No three consecutive points are co-linear.
The input file terminates with a value of 0 for N.
Output
For each tile in the input output the percentage of wasted space rounded to two digits after the decimal point. Each output must be on a separate line. Print a blank line after each output block.
Sample Input
50 0
2 0
2 2
1 1
0 2
5
0 0
0 2
1 3
2 2
2 0
0
Sample Output
Tile #1Wasted Space = 25.00 %
Tile #2
Wasted Space = 0.00 %
Rezaul Alam Chowdhury
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
struct Pt {
double x, y;
};
Pt P[1000], CH[1000];
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;
while(scanf("%d", &n) == 1 && n) {
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("Tile #%d\n", ++cases);
printf("Wasted Space = %.2lf %%\n\n", (cont-tile)*100/cont);
}
return 0;
}