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

！！平面上有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

呓,