http://poj.org/problem?id=2760
#include "stdio.h"
#include "math.h"
#include "memory.h"
#include "algorithm"
using namespace std;
#define y1 sdgdsf
double clac( double h0, double h1, double x0, double x1 ) {
return h0/(h0-h1)*( x1 - x0 ) + x0;
}
double sum[5048];
struct node {
double x;
int id;
}x[1024];
int a_to[1024], b_to[1024];
bool cmp( node a, node b ) {
if( a.x == b.x )
return a.id > b.id;
return a.x < b.x;
}
int covers[2048];
void modify( int l, int r, int a, int b, int k, int key ) {
int c = (l+r)/2, k1 = k*2+1, k2 = k*2+2;
if( a >= r || b <= l || r-l<=0 )
return;
if( a<=l && r<=b ) {
covers[ k ] += key;
if( covers[ k ] == 0 )
sum[ k ] = sum[ k1 ] + sum[ k2 ];
else
sum[ k ] = x[r].x - x[l].x;
return;
}
if( c - l > 0 )
modify( l, c, a, b, k1, key );
if( r - c > 0 )
modify( c, r, a, b, k2, key );
if( covers[ k ] == 0 )
sum[ k ] = sum[ k1 ] + sum[ k2 ];
return;
}
int n;
double x1[510], y1[510], x2[510], y2[510], h[510], lh;
double xl, xr, yu, yd, xx, yy;
struct rect {
int id;
double y;
bool in;
}r[1100];
bool cmp_rect( rect a, rect b ) {
return a.y < b.y;
}
inline void jia( double &c, double a, double b ) {
if( c < a ) c = a;
if( c > b ) c = b;
}
void input( ) {
int i;
scanf( "%d", &n );
scanf( "%lf %lf %lf %lf", &xl, &yu, &xr, &yd );
scanf( "%lf %lf %lf", &xx, &yy, &lh );
for( i=0; i<n; i++ ) {
scanf( "%lf %lf %lf %lf %lf", &x1[i], &y1[i], &x2[i], &y2[i], &h[i] );
x1[i] = clac( lh, h[i], xx, x1[i] );
jia( x1[i], xl, xr );
x2[i] = clac( lh, h[i], xx, x2[i] );
jia( x2[i], xl, xr );
y1[i] = clac( lh, h[i], yy, y1[i] );
jia( y1[i], yu, yd );
y2[i] = clac( lh, h[i], yy, y2[i] );
jia( y2[i], yu, yd );
x[i*2].x = x1[i];
x[i*2].id = i+1;
x[i*2+1].x = x2[i];
x[i*2+1].id = -(i+1);
r[i*2].id = i;
r[i*2].y = y1[i];
r[i*2].in = true;
r[i*2+1].id = i;
r[i*2+1].y = y2[i];
r[i*2+1].in = false;
}
sort( x, x+2*n, cmp );
for( i=0; i<2*n; i++ ) {
if( x[i].id >= 0 )
a_to[ x[i].id-1 ] = i;
else
b_to[ -x[i].id-1 ] = i;
}
sort( r, r+2*n, cmp_rect );
memset( covers, 0, sizeof covers );
for( i=0; i<5048; i++ )
sum[i] = 0;
}
double doit( ) {
double ans = 0;
int i, a, b;
for( i=0; i<2*n; i++ ) {
if( i )
ans += sum[0] * ( r[i].y - r[i-1].y );
a = a_to[ r[i].id ];
b = b_to[ r[i].id ];
modify( 0, n*2-1, a, b, 0, r[i].in?1:-1 );
}
return ans;
}
int main( ) {
input( );
printf( "%.4lfn", (xr-xl)*(yd-yu) - doit( ) );
return 0;
}