首页 > 代码库 > 7.14 C题

7.14 C题

题目链接:http://code.bupt.edu.cn/problem/p/415/

学姐的学弟

时间限制1000 ms内存限制 65536 KB

题目描述

学姐正在写作业,但是她写着写着就开始想学弟,走神的她就开始在纸上画圈圈。这时学弟突然出现了,好奇的学弟问学姐在做什么,惊慌之下,学姐随口说想算一下这些圆覆盖的面积为多少。学弟顿时非常仰慕学姐,但是学姐突然意识到自己不会做,为了自己能给学弟留下好印象,她来求助你帮她算出来这些圆覆盖的面积。
为了简化问题,我们假设所有圆的半径都为1。

输入格式

输入有多组数据。开头为一个整数T(T10) ,表示数据组数,接下来T组输入,每组开头为一个整数n(1n100) ,表示学姐画的圆的个数,接下来n 行,每行两个整数x i ,y i  ,表示圆的圆心坐标,1x i ,y i 100 

输出格式

输出一个数,表示面积并,精确到小数点后五位。

输入样例

1
2
1 1
2 1

输出样例

5.05482

解决这种问题,一般都不可能像初中高中那样求,要以计算机思维的方式来思考,由于数据小于100,我们可以以遍历每一个格子,分别计算面积的方式来求得累积和。对于每个格子来说,只有三种情况,,另一种就是全被圆覆盖的,只需要统计每一种出现的次数,在乘以各自图片的面积,就可以解出,值得注意的事,遍历应(0,0)遍历到(100,100),当时我只遍历到(99,99),坑了很久、、T_T


代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

const double pi=acos(-1.0);

int cir[111][111];

int main()
{
    double ans;
    double s1=pi/4;
    double s2=pi/6+sqrt(3)/4;
    double s3=1.0;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        memset(cir,0,sizeof(cir));
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            cir[x][y]=1;
        }
        for(int i=0;i<=100;i++)
            for(int j=0;j<=100;j++)
            {
                if(cir[i][j]+cir[i+1][j]+cir[i][j+1]+cir[i+1][j+1]==1)
                    ans+=s1;
                else if((cir[i][j]==1&&cir[i+1][j+1]==1)||(cir[i+1][j]==1&&cir[i][j+1]==1))
                    ans+=s3;
                else if(!(cir[i][j]+cir[i+1][j]+cir[i][j+1]+cir[i+1][j+1]==0))
                    ans+=s2;
            }
        printf("%.5f\n",ans);
    }
    return 0;
}