【解題】Area

ACM Volume CV 10589 - Area


The Problem

Measuring the area of a certain shape is an important part of certain geometric problems. When the shape becomes complex it often becomes very difficult to measure the area of that geometric shape. In some of these cases some randomized algorithms helps us immensely to find the area roughly. In this problem we will find such an area with randomized algorithm.



Look at the picture above. ABCD is a square whose sides are a. A circle is drawn (1/4 th of a circle I should say) considering A as its center. Its radius is a. Three similar circles are drawn considering B, C, D as centers. Using an algorithm based on random numbers (The random number generator may be biased) you will have to find the area of the striped region.

The idea is that you will be given N pairs of random coordinates within the rectangle. If M of them are within the striped region then the approximate area of the striped region A = (M*a²/N). You are to find the approximate area using this concept.


Input

The input file contains several sets of inputs. The description of each set is given below.

The first line of each set contains two integers N (N can always be written in the form 10^k, where k is a non-negative integer less than 6), a (100>a>=10). Each of the next N lines contains two floating-point numbers, which indicates the coordinate of a point. These floating-point numbers always have seven digits after the decimal point and the coordinates are always within the rectangle. Points just on the boundaries of the striped region are considered within the striped region. Points just outside are considered out of the striped region and vice versa. Assume that the lower left corner of the rectangle is (0, 0) and top right corner is (a, a) as shown in the figure above.

Input is terminated by a set whose N is zero.


Output

For each of input you should produce one line of output. This line should contain the area of the striped region according to the formula specified above. Your answer must be exact and no floating-point errors will be tolerated. That means precision of calculation must be infinite or precision error must be zero. Output numbers should always have five digits after the decimal point.


Sample Input

1 10
5.0000000 5.0000000
0 0


Sample Output

100.00000


解題思考

　　對於這一題，我們需要做的不是去計算圖形的斜線面積，而是根據判斷輸入資料中，點位在虛線區域中的比例乘上整個方形面積來求出來的。

　　那麼，要如何得知點是否位在虛線區域中呢？其實只要運用距離公式 (√((x₂ - x₁)² + (y₂ - y₁)²) 判斷點與四個端點 (0, 0), (0, a), (a, 0), (a, a) 的距離。若是距離都小於半徑 a，就代表這個點在斜線區域中。

　　得知有幾個點在區域中，答案就不難得出囉。


參考解答(C++)

#include <iostream>
#include <iomanip>

#define SQUARE(x) (x)*(x)

using namespace std;

int main(void)
{
    // 設定顯示至小數點第五位
    cout << setiosflags(ios::fixed) << setprecision(5);

    int n, a;
    while (1)
    {
        cin >> n >> a;
        if (!n && !a) { break; }

        int p = 0;
        for (int i = 0; i < n; i++)
        {
            double x, y;
            cin >> x >> y;

            // 判斷是否在區域中
            if (SQUARE(x) + SQUARE(y) <= SQUARE(a) &&
                SQUARE(a - x) + SQUARE(y) <= SQUARE(a) &&
                SQUARE(x) + SQUARE(a - y) <= SQUARE(a) &&
                SQUARE(a - x) + SQUARE(a - y) <= SQUARE(a))
            {
                p++;
            }
        }

        cout << static_cast<double>(p) * a * a / static_cast<double>(n) << endl;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif

    return 0;
}