分别记录x坐标和y坐标，将其分别按照从左到有的方向排序。然后对于一个输入的矩形的x，y坐标范围内的下标进行标记。以两个相邻的坐标为最小单位分割图形，最后求总面积。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 205
int mark[N][N];
double a[N],b[N];
struct node
{
double x1,y1;
double x2,y2;
}s[N];
int n;
int cmp(const void *a,const void *b)
{
return *(double *)a-*(double *)b>0?1:-1;
}
int Find(double *a,double x)
{
int l,r,mid;
l=0;
r=2*n-1;
while(l<=r)
{
mid=(l+r)/2;
if(a[mid]==x)
return mid;
else if(a[mid]<x)
l=mid+1;
else
r=mid-1;
}
return 0;
}
int main()
{
int cnt=1;
while(scanf("%d",&n),n)
{
int i,j,k;
for(i=0,j=0;i<n;i++)
{
scanf("%lf%lf%lf%lf",&s[i].x1,&s[i].y1,&s[i].x2,&s[i].y2);
a[j]=s[i].x1;
b[j]=s[i].y1;
j++;
a[j]=s[i].x2;
b[j]=s[i].y2;
j++;
}
qsort(a,2*n,sizeof(a[0]),cmp);
qsort(b,2*n,sizeof(b[0]),cmp);
memset(mark,0,sizeof(mark));
double area=0;
for(i=0;i<n;i++)
{
int f1,f2,f3,f4;
f1=Find(a,s[i].x1);
f2=Find(b,s[i].y1);
f3=Find(a,s[i].x2);
f4=Find(b,s[i].y2);
for(j=f1;j<f3;j++)
{
for(k=f2;k<f4;k++)
mark[j][k]=1;
}
}
for(i=0;i<2*n;i++)
{
for(j=0;j<2*n;j++)
area+=(a[i+1]-a[i])*(b[j+1]-b[j])*(double)mark[i][j];
}
printf("Test case #%d
",cnt++);
printf("Total explored area: %.2f
",area);
}
return 0;
}