Problem Solving►UVa

UVa 356 - Square Pegs And Round Holes

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

中文網址

Solution

只需要算四分之一即可，最後再乘 4 即是整張棋盤的了。取右上的那部分棋盤，利用每個小方塊 左下角的點 和 右上角 的來判斷是否在圓內、部分或都不是。跑 $O(n^2)$ 窮舉每個方塊。

Code

UVa 356
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<cstdio>
#include<cmath>

inline double getDis(int x, int y)
{
    return sqrt(x*x + y*y);
}
int main()
{
    int n;
    bool first = true;
    while (scanf("%d", &n) != EOF)
    {
        int all = 0, part = 0;
        double r = n - 0.5;
        for (int x = 0; x < n; x++)
            for (int y = 0; y < n; y++)
            {
            double d1 = getDis(x, y), d2 = getDis(x + 1, y + 1);//左下角、右下角
            if (d2 <= r)
                all++;
            else if (d1 < r)
                part++;
            }

        if (first)
            first = false;
        else putchar('\n');

        printf("In the case n = %d, %d cells contain segments of the circle.\n", n, part*4);
        printf("There are %d cells completely contained in the circle.\n", all*4);
    }

    return 0;
}