解二: 可以把相互重叠的块都切割出来,一个小块一个小块的计算面积的总和就行了.
解一: 这个方法不是线段树的,先放这吧,用线段树做出来后再编辑,
其中的map[ ][ ]很好,,
#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<stack>
#include<math.h>
#include<string>
#include<stdlib.h>
#include<list>
#include<vector>
using namespace std;
#define N 500
int map[N][N];
double ans[N][5];
int main()
{
int i,j,k;
int t;
int n;
double x[N*2],y[N*2];
int num=0;
while (cin>>n,n)
{
num++;
j=0;
for (i=0;i<n;i++)
{
cin>>ans[i][0]>>ans[i][1]>>ans[i][2]>>ans[i][3];
y[j]=ans[i][1];
x[j++]=ans[i][0];
y[j]=ans[i][3];
x[j++]=ans[i][2];
}
sort(x,x+2*n);
sort(y,y+2*n);
memset(map,0,sizeof(map));
for (i=0;i<n;i++)
{
int j1,j2,i1,i2;
for (i1=0;i1<2*n;i1++)
if (x[i1]==ans[i][0])
break;
for (i2=i1;i2<2*n;i2++)
if (x[i2]==ans[i][2])
break;
for (j1=0;j1<2*n;j1++)
if (y[j1]==ans[i][1])
break;
for (j2=j1;j2<2*n;j2++)
if (y[j2]==ans[i][3])
break;
//cout<<i1<<' '<<i2<<' '<<j1<<' '<<j2<<endl;
for (k=i1;k<i2;k++)
{
for (j=j1;j<j2;j++)
{
map[k][j]=1;
}
}
}
double sum=0.00;
for (i=0;i<2*n;i++)
{
for (j=0;j<2*n;j++)
sum+=(double)map[i][j]*(x[i+1]-x[i])*(y[j+1]-y[j]);
}
printf("Test case #%d\nTotal explored area: %.2f\n\n",num,sum);
}
return 1;
}
2 10 10 20 20 15 15 25 25.5 0
Test case #1 Total explored area: 180.00