[UVA] 10060 - A hole to catch a man
Problem F
A Hole to Catch a Man
Input : standard input
Output : standard output
How can a manhole be a hole if it is covered? Perhaps, to prove a manhole a hole, most of the manholes of Dhaka are uncovered. So now manhole means a hole to catch a man. Anyway, the new Mayor of Dhaka does not like this definition and he has recently been highly acclaimed by general people for ordering corresponding department to cover all the manholes of the city within a month.
Manhole Cover Manufacturing Corporation (MCMC) somehow managed to get the order. (Yes, this is a big deal, since a lot of manhole covers are to be made). MCMC makes the cover using steel, and they import polygonal steel sheets of different shapes and thickness from abroad. Then they melt the sheets to make the circular manhole covers, which also differ in size and thickness.
MCMC needs a program which, given dimensions of a number of steel sheets, will calculate how many manhole cover can be made from these sheets. You are to help them by writing the program.
Input
The input file consists of several data blocks.
Each data block starts with an integer N, the number of polygonal steel sheets. i’th line of the next N lines starts with thickness of the i’th sheet followed by co-ordinates of the polygons’ corner points in some order (clockwise or anti-clockwise). Each line consists of a series of real numbers in following format:
Ti X0 Y0 X1 Y1 X2 Y2 … … Xn Yn X0 Y0
Where Ti is the thickness of the sheet, and Xi Yi are the coordinates of corner points. The line ends with co-ordinate of the first point. Last line of each data block will have two real numbers, R and T, radius and thickness of the manhole cover respectively.
Input file ends with a data block with N = 0.
Output
For each data block, print the number of manhole cover in separate line.
Sample Input:
22 0 0 0 10 5 15 12 10 10 0 0 0
5 0 0 5 100 100 0 0 0
5 3
1
2 0 0 10 0 10 10 0 10 0 0
5 2
0
Sample Output:
1071
___________________________________________________________________________________________
Rezaul Alam Chowdhury, Suman Kumar Nath, Tarique Mesbaul Islam.
題目描述：
現在進口一些鐵板，每個鐵板是個多邊形，而且具有不同的厚度。現在水溝蓋固定半徑 r, 厚度要 t。
問這些鐵板最多可以做出多少水溝蓋。
題目解法：
得到多邊形面積後，可以計算出體積，把所有體積加總之後，去除每個水溝蓋的體積。
相當於把鐵板全都融了。
#include <stdio.h>
#include <math.h>
struct Pt {
double x, y;
};
int main() {
int n, i;
Pt D[1005];
const double pi = acos(-1);
while(scanf("%d", &n) == 1 && n) {
double V = 0, t, r;
while(n--) {
scanf("%lf", &t);
scanf("%lf %lf", &D[0].x, &D[0].y);
#define eps 1e-6
int m = 1;
while(scanf("%lf %lf", &D[m].x, &D[m].y) == 2) {
if(fabs(D[m].x-D[0].x) < eps && fabs(D[m].y-D[0].y) < eps)
break;
m++;
}
double area = 0;
for(i = 0; i < m; i++)
area += D[i].x*D[i+1].y - D[i].y*D[i+1].x;
area = fabs(area)/2;
V += area * t;
}
scanf("%lf %lf", &r, &t);
printf("%d\n", (int)(V/(r*r*pi*t)));
}
return 0;
}