#include<stdio.h>
#include<math.h>
#define SIZE 110

struct Circle{
	int x,y,r;
}circle[SIZE];
struct Max{
	int lx,rx,uy,dy;
}max[SIZE];
bool map[SIZE][SIZE];
int flag[SIZE],n;
bool link(int i, int j){
	if(abs(circle[i].x-circle[j].x)<=circle[i].r+circle[j].r && abs(circle[i].y-circle[j].y)<=circle[i].r+circle[j].r)
		return true;
	return false;
}
void dfs(int k,int f)
{
	int i;
	for(i = 0; i < n; i++)
		if(map[k][i] && !flag[i]){
			flag[i] = f;
			dfs(i,f);
		}
}
int main()
{
	int w,h,i,j;
	scanf("%d%d%d",&w,&h,&n);
	for(i = 0; i < n; i++)
		scanf("%d%d%d",&circle[i].x,&circle[i].y,&circle[i].r);
	for(i = 0; i < n; i++){
		for(j = i+1; j < n; j++)
			if(link(i,j))
				map[i][j] = map[j][i] = 1;
	}
	int f = 1,e;
	for(i = 0; i < n; i++){
		if(!flag[i]){
			flag[i] = f;
			dfs(i,f);
			f++;
		}
	}
	for(i = 1; i < f; i++){
		max[i].lx = 1000000;
		max[i].rx = 0;
		max[i].uy = 0;
		max[i].dy = 1000000;
	}
	for(i = 0; i < n; i++){
		e = flag[i];
		if(circle[i].x+circle[i].r > max[e].rx)
			max[e].rx = circle[i].x+circle[i].r;
		if(circle[i].x-circle[i].r < max[e].lx)
			max[e].lx = circle[i].x-circle[i].r;
		if(circle[i].y+circle[i].r > max[e].uy)
			max[e].uy = circle[i].y+circle[i].r;
		if(circle[i].y-circle[i].r < max[e].dy)
			max[e].dy = circle[i].y-circle[i].r;
	}
	int out = w*h;
	for(i = 1; i < f; i++)
		out -= ((max[i].rx-max[i].lx)*(max[i].uy-max[i].dy));
	printf("%d\n",out);
	return 0;
}

• 怎么没人啊 ，自己顶！！！！ (1621) ACM06021fly 2006-10-02 11:14:40
  • 来个人帮忙看一下啊 (0) ACM06021fly 2006-10-02 11:15:00