2014-05-21

UVa 10320 - Cow Trouble! Help Please

1. Problem
2. Input
3. Output
4. Sample Input
5. Sample Output
6. Solution

Problem

There are many classic problem with cows/goats and grass field in the world of mathematics. One of such problems is shown in the picture (left one) below. A goat is tied at point C which is on the edge of a round field with a rope of length R. One has to determine the length R when the cow can eat 50% grass of the round field. But in this problem we will consider a slightly different scenario which is shown in the second figure. In a field of infinite area there is a house ABDC. A cow is tied with pillar B of the house with a rope of length R. The length and width of the house is l and w. If the house was not there the cow could eat all the grass in the round green field (The round green field is a circle of radius R). But the presence of the house will certainly reduce his ability as the cow cannot enter the house nor can any part of the rope. You will have to determine the area the cow can now roam around and eat grass.

Fig 1: A classic Problem with a Goat

Fig 2: The Current Classic Problem with Cow

Input

The input file contains several lines of input. Each line contains three floating point numbers l, w and R as described in the problem statement. All numbers are less than 10000. Input is terminated by end of file.

Output

For each line of input produce one line of output. This output denotes the area that the cow can cover by not entering the house. This value should contain ten digits after the decimal point. Output will be checked with special judge. So you should not worry about very small precision errors.

Sample Input

1 2	10 5 5 10 4 8

Sample Output

1 2	58.9048622548 163.3628179867

Solution

題目描述：
有一頭牛被一根長度 R 的繩子拴在一棟建築物 ABCD 的 B 點上，草地的範圍為無限大，求牛可以吃到的草的範圍。Input 會給l, w 和 R 表示建築物長寬和繩長；l, w, R < 10000。Output 要輸到小數點第 10 位。

題目解法：

就是根據 R 的四種情況去討論，其中最麻煩的是對於 R > l + w，這種情況會需要討論重疊的區域，算出三角形夾角然後分別算兩個扇形面積，再弄回重疊區域三角形中的哪一塊有草。

其實這一題的題解網路上是有的，但是 PO 出來是因為自己卡在 WA，原因是這樣子的，假使 A = 0.5 * B 和 A = B / 2，這兩者寫法並無不同，但是後者的精準度比較好，很多次的 WA 都掛在這一點。

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int main() {
    double w, l, r;
    const double pi = acos(-1);
    while(scanf("%lf %lf %lf", &l, &w, &r) == 3) {
        if(w > l)
            swap(w, l);
        double area;
        if(r <= w)
            area = r * r * pi * 3 / 4.0;
        else if(r <= l)
            area = r * r * pi * 3 / 4.0 + (r - w) * (r - w) * pi / 4.0;
        else if(r <= l + w)
            area = r * r * pi * 3 / 4.0 + (r - w) * (r - w) * pi / 4.0 
                    + (r - l) * (r - l) * pi / 4.0;
        else {
            double a = atan2(l, w), b, c;
            double la, lb, lc;
            
            la = hypot(w, l);
            lb = r - w;
            lc = r - l;
            b = acos((la*la + lb*lb - lc*lc)/(2*la*lb)) + a;
            c = acos((la*la + lc*lc - lb*lb)/(2*la*lc)) + (pi /2) - a;
                        
            area = r * r * pi * 3 / 4.0;
            area += (r - w) * (r - w) * (pi - b) / 2;
            area += (r - l) * (r - l) * (pi - c) / 2;
            area += lb * la * sin(b - a) / 2;
            area -= w * l / 2;
        }
        printf("%0.10lf\n", area);			
    }
    return 0;
}

Morris' Blog