~~求教一道看上去挺简单的算法题,,谢谢~~

时间:2021-08-18 12:24:37
!!平面上有n个圆,任意两个不同的圆之间只有相离(可以外切)和包含(可以内切)两种关系。初始时整个平面是黑色的,我们按照输入给定的顺序在平面上画出这些圆,我们画一个圆的时候,把这个圆覆盖的区域全部反色,即如果区域中的一个点原来是黑色,则将它涂为白色;如果这个点原来是白色,则将它涂成黑色。
按照这个步骤把所有的圆都画出来后,请输出平面上的所有白色区域的面积之和。

!!输入格式
输入文件的第一行有一个整数n,表示圆的个数。以下n行,每行用三个整数x, y和r描述一个圆,表示圆心(x, y)和半径r。在平面上画圆的顺序和输入给定的顺序相同。
!!输出格式
你只需要向输出文件输入一个实数,精确到小数点后两位,表示平面上白色区域面积之和。

!!输入样例
3
0 0 5
0 1 2
10 10 1
!!输出样例
69.12

我感觉这个挺简单的啊,就是记录下每个圆被嵌套的重述,结果是7组测试数据只有3组正确,37%,请高手们说说哪些重要环节或者情况漏掉了,谢谢
#include <stdio.h>
#include <stdlib.h>
typedef struct{
int x;
int y;
int r;
int n;
}circle;
int isIn(circle *c, int i, int j)
{//判j圆要是在i圆中,则返回1
if(c[i].x+c[i].r>=c[j].x+c[j].r && c[i].x-c[i].r<=c[j].x-c[j].r && 
c[i].y+c[i].r>=c[j].y+c[j].r && c[i].y-c[i].r<=c[j].x+c[j].r)
return 1;
else
return 0;
}
int main()
{
int n, i, j, sum=0;
circle *c;
freopen("circles.in", "r", stdin);
freopen("circles.out", "w", stdout);

scanf("%d", &n);
c=(circle *)malloc(n*sizeof(circle));
for(i=0; i<n; i++)
{
scanf("%d%d%d", &c[i].x, &c[i].y, &c[i].r);
c[i].n=0;
for(j=0; j<i; j++)
{
if(isIn(c, i, j)==1)//第j个圆在第i个圆里
c[j].n++;
else if(isIn(c, j, i)==1)//第i个圆在第j个圆里
c[i].n++;
}
}
for(i=0; i<n; i++)
{
if(c[i].n%2==0) sum+=c[i].r*c[i].r;
else sum-=c[i].r*c[i].r;
}
printf("%f\n", sum*3.141592653589793);
}

15 个解决方案

#1


#include <stdio.h>
#include <stdlib.h>
typedef struct{
int x;
int y;
int r;
int n;
}circle;
int isIn(circle *c, int i, int j)
{//判j圆要是在i圆中,则返回1
if(c[i].x+c[i].r>=c[j].x+c[j].r && c[i].x-c[i].r<=c[j].x-c[j].r && 
c[i].y+c[i].r>=c[j].y+c[j].r && c[i].y-c[i].r<=c[j].x+c[j].r)
return 1;
else
return 0;
}
int main()
{
int n, i, j, sum=0;
circle *c;
freopen("circles.in", "r", stdin);
freopen("circles.out", "w", stdout);

scanf("%d", &n);
c=(circle *)malloc(n*sizeof(circle));
for(i=0; i<n; i++)
{
scanf("%d%d%d", &c[i].x, &c[i].y, &c[i].r);
c[i].n=0;
for(j=0; j<i; j++)
{
if(isIn(c, i, j)==1)//第j个圆在第i个圆里
c[j].n++;
else if(isIn(c, j, i)==1)//第i个圆在第j个圆里
c[i].n++;
}
}
for(i=0; i<n; i++)
{
if(c[i].n%2==0) sum+=c[i].r*c[i].r;
else sum-=c[i].r*c[i].r;
}

printf("%f\n", sum*3.141592653589793);
}

#2


是否需要考虑非整形的情况,如x=1.2,y=2.0,r = 4等

#3


还有一个考虑sum超出int边界

#4


引用 2 楼 StarRaino 的回复:
是否需要考虑非整形的情况,如x=1.2,y=2.0,r = 4等


不行啊,改成浮点数也是37%的正确,而且人家题目很明确:输入每行是三个整数来描述一个圆

大家再帮着想想,我现在感觉不是那么简单

#5


大家帮忙看看吧,谢谢了

#6


可以先用数组保存圆的信息。

然后对有包含关系的圆进行排序。处在奇数位的圆的面积就相加,偶数位的就相减。

对无包含关系的圆(相离)的面积相加,最后就可以准确计算出白色区域的面积了。

数组保存圆的数据 和 圆的包含关系以及排序是关键。搞定了就可以写出程序了。

#7


isIn函数中if语句里的最后一个判断条件c[i].y-c[i].r <=c[j].x+c[j].r是不是写错了。
另外若圆的关系只有两种,是不是可以直接判断圆i的圆心在不在圆j内来确定两圆的位置。

#8


引用 7 楼 VirGhost 的回复:
isIn函数中if语句里的最后一个判断条件c[i].y-c[i].r <=c[j].x+c[j].r是不是写错了。 
另外若圆的关系只有两种,是不是可以直接判断圆i的圆心在不在圆j内来确定两圆的位置。


谢谢,最后一个条件是不对,c[i].y-c[i].r<=c[j].y-c[j].r,改了以后正确率是50%
狂晕

还有你说的这种方法我觉得不大可行吧,i的圆心在j的圆内,那么i和j两种关系都有可能

#9


6楼,我就是用的这个方法啊,现在只对一半

#10


在哪里测试

#11


引用 7 楼 VirGhost 的回复:

#12


引用 10 楼 VirGhost 的回复:
在哪里测试

这个是天津大学的在线评测,给你地址
http://oi.tju.edu.cn/problem/view/1012.html

右上面有个提交,应该是要1分钟注册下用户名,不错的网站,推荐下

#13


是不是
            if(isIn(c, i, j)==1)//第j个圆在第i个圆里
                c[j].n++;
            else if(isIn(c, j, i)==1)//第i个圆在第j个圆里
                c[i].n++;
错误,改成 
           if(isIn(c, i, j)==1)//第j个圆在第i个圆里
                c[j].n=c[i].n+1;
            else if(isIn(c, j, i)==1)//第i个圆在第j个圆里
                c[i].n=c[j].n+1;

这样试试看。那个在线评测网页无法打开。

#14


引用 13 楼 Rorbin007 的回复:
是不是 
            if(isIn(c, i, j)==1)//第j个圆在第i个圆里 
                c[j].n++; 
            else if(isIn(c, j, i)==1)//第i个圆在第j个圆里 
                c[i].n++; 
错误,改成 
          if(isIn(c, i, j)==1)//第j个圆在第i个圆里 
                c[j].n=c[i].n+1; 
            else if(isIn(c, j, i)==1)//第i个圆在第j个圆里 
                c[i].n=c[j].n+1; 

这样试试看。那个在线评测网页无法…


感觉没有道理啊,你这是什么意思

#15


呓,

#1


#include <stdio.h>
#include <stdlib.h>
typedef struct{
int x;
int y;
int r;
int n;
}circle;
int isIn(circle *c, int i, int j)
{//判j圆要是在i圆中,则返回1
if(c[i].x+c[i].r>=c[j].x+c[j].r && c[i].x-c[i].r<=c[j].x-c[j].r && 
c[i].y+c[i].r>=c[j].y+c[j].r && c[i].y-c[i].r<=c[j].x+c[j].r)
return 1;
else
return 0;
}
int main()
{
int n, i, j, sum=0;
circle *c;
freopen("circles.in", "r", stdin);
freopen("circles.out", "w", stdout);

scanf("%d", &n);
c=(circle *)malloc(n*sizeof(circle));
for(i=0; i<n; i++)
{
scanf("%d%d%d", &c[i].x, &c[i].y, &c[i].r);
c[i].n=0;
for(j=0; j<i; j++)
{
if(isIn(c, i, j)==1)//第j个圆在第i个圆里
c[j].n++;
else if(isIn(c, j, i)==1)//第i个圆在第j个圆里
c[i].n++;
}
}
for(i=0; i<n; i++)
{
if(c[i].n%2==0) sum+=c[i].r*c[i].r;
else sum-=c[i].r*c[i].r;
}

printf("%f\n", sum*3.141592653589793);
}

#2


是否需要考虑非整形的情况,如x=1.2,y=2.0,r = 4等

#3


还有一个考虑sum超出int边界

#4


引用 2 楼 StarRaino 的回复:
是否需要考虑非整形的情况,如x=1.2,y=2.0,r = 4等


不行啊,改成浮点数也是37%的正确,而且人家题目很明确:输入每行是三个整数来描述一个圆

大家再帮着想想,我现在感觉不是那么简单

#5


大家帮忙看看吧,谢谢了

#6


可以先用数组保存圆的信息。

然后对有包含关系的圆进行排序。处在奇数位的圆的面积就相加,偶数位的就相减。

对无包含关系的圆(相离)的面积相加,最后就可以准确计算出白色区域的面积了。

数组保存圆的数据 和 圆的包含关系以及排序是关键。搞定了就可以写出程序了。

#7


isIn函数中if语句里的最后一个判断条件c[i].y-c[i].r <=c[j].x+c[j].r是不是写错了。
另外若圆的关系只有两种,是不是可以直接判断圆i的圆心在不在圆j内来确定两圆的位置。

#8


引用 7 楼 VirGhost 的回复:
isIn函数中if语句里的最后一个判断条件c[i].y-c[i].r <=c[j].x+c[j].r是不是写错了。 
另外若圆的关系只有两种,是不是可以直接判断圆i的圆心在不在圆j内来确定两圆的位置。


谢谢,最后一个条件是不对,c[i].y-c[i].r<=c[j].y-c[j].r,改了以后正确率是50%
狂晕

还有你说的这种方法我觉得不大可行吧,i的圆心在j的圆内,那么i和j两种关系都有可能

#9


6楼,我就是用的这个方法啊,现在只对一半

#10


在哪里测试

#11


引用 7 楼 VirGhost 的回复:

#12


引用 10 楼 VirGhost 的回复:
在哪里测试

这个是天津大学的在线评测,给你地址
http://oi.tju.edu.cn/problem/view/1012.html

右上面有个提交,应该是要1分钟注册下用户名,不错的网站,推荐下

#13


是不是
            if(isIn(c, i, j)==1)//第j个圆在第i个圆里
                c[j].n++;
            else if(isIn(c, j, i)==1)//第i个圆在第j个圆里
                c[i].n++;
错误,改成 
           if(isIn(c, i, j)==1)//第j个圆在第i个圆里
                c[j].n=c[i].n+1;
            else if(isIn(c, j, i)==1)//第i个圆在第j个圆里
                c[i].n=c[j].n+1;

这样试试看。那个在线评测网页无法打开。

#14


引用 13 楼 Rorbin007 的回复:
是不是 
            if(isIn(c, i, j)==1)//第j个圆在第i个圆里 
                c[j].n++; 
            else if(isIn(c, j, i)==1)//第i个圆在第j个圆里 
                c[i].n++; 
错误,改成 
          if(isIn(c, i, j)==1)//第j个圆在第i个圆里 
                c[j].n=c[i].n+1; 
            else if(isIn(c, j, i)==1)//第i个圆在第j个圆里 
                c[i].n=c[j].n+1; 

这样试试看。那个在线评测网页无法…


感觉没有道理啊,你这是什么意思

#15


呓,