3960495_ac_16ms_204k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h> 
typedef struct 
{ 
int xmin,xmax; /* [xmin,xmax],表示圆在X轴上投影所对应的区间 */ 
int ymin,ymax; /* [ymin,ymax],表示圆在Y轴上投影所对应的区间 */ 
int mark; /* 0 表示独立,1 表示与其它圆有touch 或overlap */ 
}CIRCLE; 


int is_touch(CIRCLE a,CIRCLE b) /* 判断两个圆是否 touch 或overlap */ 
{ 
if(b.xmin>a.xmax || b.xmax<a.xmin) 
return 0; 
if(b.ymin>a.ymax || b.ymax<a.ymin) 
return 0; 
return 1; 
} 

int main() 
{ 
int L,W; 
int N; 
CIRCLE cir[100]; 
int i,j,k,touch,x,y,r; 
long sum,area; 
while(scanf("%d%d%d",&L,&W,&N)!=EOF) 
{ 
for(i=0;i<N;i++) 
{ 
scanf("%d%d%d",&x,&y,&r); 
cir[i].xmin=x-r; 
cir[i].xmax=x+r; 
cir[i].ymin=y-r; 
cir[i].ymax=y+r; 
cir[i].mark=0; 
} 
for(i=0;i<N;) 
{ 
if(!cir[i].mark) 
{ 
touch=0; 
for(j=0;j<N && !touch;) 
if(j!=i && !cir[j].mark && is_touch(cir[i],cir[j])) 
touch=1; 
else 
j++; 
if(touch) 
{ 
/* 组合成一个更大的矩形 */ 
cir[i].xmin=cir[i].xmin<cir[j].xmin?cir[i].xmin:cir[j].xmin; 
cir[i].xmax=cir[i].xmax>cir[j].xmax?cir[i].xmax:cir[j].xmax; 
cir[i].ymin=cir[i].ymin<cir[j].ymin?cir[i].ymin:cir[j].ymin; 
cir[i].ymax=cir[i].ymax>cir[j].ymax?cir[i].ymax:cir[j].ymax; 
cir[j].mark=1; 
} 
else 
i++; 
} 
else 
i++; 
} 
sum=0; 
for(i=0;i<N;i++) 
if(!cir[i].mark) 
sum+=(cir[i].xmax-cir[i].xmin)*(cir[i].ymax-cir[i].ymin); 
area=L*W-sum; 
printf("%ld\n",area); 
} 
return 0; 
}