Poj Solution 2760

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;
}