[UVA] 10060 - A hole to catch a man＠Morris' Blog

2013-07-05 11:30:08| 人氣910| 回應0 | 上一篇 | 下一篇

[UVA] 10060 - A hole to catch a man

推薦 0 收藏 0 轉貼0 訂閱站台

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:

T_i X₀ Y₀ X₁ Y₁ X₂ Y₂ … … X_n Y_n X₀ Y₀

Where T_i is the thickness of the sheet, and X_i Y_i 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:

2
2 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:

107
1
___________________________________________________________________________________________
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;
}

我要檢舉

#10060#A hole to catch a man

台長： Morris

您可能對以下文章有興趣

[UVA] 10488 - Swimming Gopher

[UVA] 11201 - The problem of the crazy linguist

[UVA] 12150 - Pole Position

c112. Optimal Array Multiplication Sequence

人氣(910) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][組合] 12028 - A Gift from the Setter
此分類上一篇:[UVA][模擬] 10016 - Flip-Flop the Squarelotron

回應(0)