卡了我很久的题了，今天下决心弄，总算弄过了
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
const int N=110;
const double eps= 1e-8;
struct Node
{
int l, r, cover;
double len;
}tree[N*8];
struct Line
{
double x, y1, y2;
bool flag;
}line[N*2];
double temp[N*2], yline[N*2];
int n;
int cmpdy(double a, double b)
{
return (a-b) > eps ? 1 : -1;
}
bool dd(double a, double b)
{
return fabs(a-b)<eps ? 1 : 0;
}
bool dy(double a, double b)
{
return a-b>eps ? 1 : 0;
}
int cmpt(const void *a , const void *b)
{
return cmpdy(*(double *)a, *(double *)b);
}
int cmpL(const void *a, const void *b)
{
return cmpdy((*(Line *)a).x, (*(Line *)b).x);
}
void build(int l, int r, int p)
{
tree[p].l= l;
tree[p].r= r;
tree[p].cover= 0;
tree[p].len= 0;
if ( r-l > 1 )
{
int mid= l+r >> 1;
build(l, mid, 2*p);
build(mid, r, 2*p+1);
}
}
void update(int p)
{
if ( tree[p].cover > 0 )
tree[p].len= yline[tree[p].r-1] - yline[tree[p].l-1];
else if ( tree[p].r - tree[p].l <= 1)
tree[p].len= 0;
else tree[p].len= tree[2*p].len+tree[2*p+1].len;
}
void insert(int l, int r, int p)
{
if ( l <= tree[p].l && tree[p].r <= r )
{
tree[p].cover++;
update(p);
return;
}
if ( tree[p].r - tree[p].l <= 1 )
return;
int mid= tree[p].l+tree[p].r >> 1;
if ( l < mid )
insert(l, r, 2*p);
if ( mid < r )
insert(l, r, 2*p+1);
update(p);
}
void del(int l, int r, int p)
{
if ( l <= tree[p].l && tree[p].r <= r )
{
tree[p].cover--;
update(p);
return;
}
if ( tree[p].r - tree[p].l <= 1 )
return;
int mid= tree[p].l+tree[p].r >> 1;
if ( l < mid )
del(l, r, 2*p);
if ( mid < r )
del(l, r, 2*p+1);
update(p);
}
int getindex(int n, double num)
{
int left= 0, right= n-1, mid;
while ( left < right )
{
mid= left+right>>1;
if ( dy(num, yline[mid]) )
left= mid+1;
else right= mid;
}
return right + 1;
}
int main()
{
int icase= 1;
while ( scanf("%d", &n), n )
{
int i, m= 1;
double x1, x2, y1, y2;
for ( i = 0 ; i < n ; i++ )
{
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
line[2*i].x= x1;
line[2*i].y1= y1;
line[2*i].y2= y2;
line[2*i].flag= 1;
line[2*i+1].x= x2;
line[2*i+1].y1= y1;
line[2*i+1].y2= y2;
line[2*i+1].flag= 0;
temp[2*i]= y1;
temp[2*i+1]= y2;
}
n <<= 1;
qsort(temp, n, sizeof(double), cmpt);
qsort(line, n, sizeof(Line), cmpL);
yline[0]= temp[0];
for ( i = 1 ; i < n ; i++ )
if ( !dd(yline[m-1], temp[i]) )
yline[m++]= temp[i];
build(1, m, 1);
double area= 0;
for ( i = 0 ; i < n-1 ; i++ )
{
int l= getindex(m, line[i].y1), r= getindex(m, line[i].y2);
if ( line[i].flag )
insert(l, r, 1);
else
del(l, r, 1);
area+=tree[1].len*(line[i+1].x-line[i].x);
}
printf("Test case #%d\nTotal explored area: %.2f\n\n", icase++, area);
}
return 0;
}