UVA 356 SquarePegs And Round Holes(点到圆心的距离)

UVA 356 SquarePegs And Round Holes(点到圆心的距离)

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=292

题意:

一个直径为2*n-1单位长度的圆被画在了2n*2n的网格棋盘中间.现在要你求出有多少个小格子是被圆包含的,有多少个小格子是被圆相交的?

分析:

我们假设网格棋盘左上角的坐标为(0,0), 那么圆心坐标为(n,n).

那么第一个网格(第0行0列的网格)由 (0,0),(0,1),(1,0),(1,1) 这4个网格点构成. 第i行j列的网格由(i,j),(i+1,j),(i,j+1),(i+1,j+1)这4个网格点构成.

所以如果一个网格被圆完全包围,那么它的4个角上的点距离圆心必然<=半径.

如果一个网格的4个角上的点距离圆心都>=半径,那么该网格必然在圆外.

剩下的情况就是网格与圆相交了.

直接2重循环判断每个网格的情况即可.

AC代码:

#include<cstdio>
#include<cmath>
using namespace std;
int n;
double dist(int i,int j)//(i,j)点到圆心的距离
{
    return sqrt((n-i)*(n-i)+(n-j)*(n-j));
}

int main()
{
    bool flag=false;
    while(scanf("%d",&n)==1)
    {
        if(flag) printf("\n");
        flag=true;
        int num_in=0;   //在圆内的网格数
        int num_cross=0;//与圆相交的网格数
        for(int i=0;i<2*n;++i)
        for(int j=0;j<2*n;++j)
        {
            if(dist(i,j)<=n-0.5 && dist(i+1,j)<=n-0.5 && dist(i,j+1)<=n-0.5 && dist(i+1,j+1)<=n-0.5 )
                ++num_in;
            else if(dist(i,j)>=n-0.5 && dist(i+1,j)>=n-0.5 && dist(i,j+1)>=n-0.5 && dist(i+1,j+1)>=n-0.5 )
                continue;
            else
                ++num_cross;
        }
        printf("In the case n = %d, %d cells contain segments of the circle.\n",n,num_cross);
        printf("There are %d cells completely contained in the circle.\n",num_in);
    }
    return 0;
}