2760.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2760  User Id:fzk 
#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( "%.4lf\n", (xr-xl)*(yd-yu) - doit( ) );
	return 0;
}