具体的就不多解释了，当线段树练练手吧。
#include <cstdio>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
using namespace std;
const int root = 0;
const double eps = 1e-8;
struct Node{
int l,r,cover;
int lnd,rnd;
double len;
}node[10000];
int cnt,cnty;
double indx[210];
struct Line{
double x,y1,y2;
bool f;
}line[210];
void Creat(int p,int l,int r)
{
node[p].l = l; node[p].r = r;
node[p].len = 0.0; node[p].cover = 0;
if (r - l > 1)
{
int mid = (l + r) >> 1;
node[p].lnd = ++cnt;
Creat(cnt,l,mid);
node[p].rnd = ++cnt;
Creat(cnt,mid,r);
}
else {node[p].lnd = node[p].rnd = -1;}
}
void upData(int p)
{
if (node[p].cover > 0)
{
node[p].len = indx[node[p].r] - indx[node[p].l];
}
else if (node[p].l == node[p].r - 1)
{
node[p].len = 0.0;
node[p].cover = 0;
}
else {
int lf = node[p].lnd;
int rf = node[p].rnd;
node[p].len = node[lf].len + node[rf].len;
}
}
void Insert(int p,int l,int r)
{
// printf("p = %d,[%d,%d]\n",p,l,r);
if (l <= node[p].l && node[p].r <= r)
node[p].cover++;
else {
int mid = (node[p].l + node[p].r) >> 1;
if (mid > l)
Insert(node[p].lnd,l,r);
if (mid < r)
Insert(node[p].rnd,l,r);
}
upData(p);
}
void Delete(int p,int l,int r)
{
if (l <= node[p].l && node[p].r <= r)
node[p].cover--;
else {
int mid = (node[p].l + node[p].r) >> 1;
if (mid > l)
Delete(node[p].lnd,l,r);
if (mid < r)
Delete(node[p].rnd,l,r);
}
upData(p);
}
int Bi_Search(double key)
{
int l = 1,r = cnty + 1,mid;
while (l < r)
{
mid = (l + r) >> 1;
if (fabs(indx[mid] - key) < eps)
return mid;
else if (indx[mid] + eps < key)
l = mid + 1;
else r = mid;
}
}
void Init_Index()
{
sort(indx+1,indx+1+cnty);
int m = 1;
for (int i = 2; i <= cnty; i++)
if (fabs(indx[i] - indx[i-1]) > eps)
{
// printf("%lf \n",indx[i]);
m ++;
indx[m] = indx[i];
}
cnty = m;
}
bool cmp(const Line &a,const Line &b)
{
return a.x < b.x;
}
int main()
{
int n,i,j,k,left,right,cas = 1;
double x1,x2,y1,y2,prelen,ans,ny1,ny2;
while (scanf("%d",&n) && n)
{
for (i = 1; i <= n + n; i+=2)
{
scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
ny1 = min(y1,y2);
ny2 = max(y2,y1);
line[i].x = x1; line[i].y1 = ny1; line[i].y2 = ny2;
line[i].f = true;
line[i+1].x = x2; line[i+1].y1 = ny1; line[i+1].y2 = ny2;
line[i+1].f = false;
indx[i] = y1; indx[i+1] = y2;
}
sort(line+1,line+1+n+n,cmp);
cnty = n + n;
Init_Index();
// printf("cnty = %d\n",cnty);
Creat(root,1,cnty);
left = Bi_Search(line[1].y1);
right = Bi_Search(line[1].y2);
Insert(root,left,right);
prelen = node[root].len;
ans = 0;
for (i = 2; i <= n+n ;i++)
{
left = Bi_Search(line[i].y1);
right = Bi_Search(line[i].y2);
if (line[i].f)
Insert(root,left,right);
else Delete(root,left,right);
ans += prelen*(line[i].x - line[i-1].x);
prelen = node[root].len;
// printf("i = %d,len = %lf\n",i,prelen);
}
printf("Test case #%d\n",cas++);
printf("Total explored area: %.2lf\n\n",ans);
}
return 0;
}