3168.txt

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

Source

Problem Id:3168  User Id:fzk 
Memory:1660K  Time:746MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <memory.h>
#include <algorithm>

bool sign[25000];

struct corner {
	int x, y;
	int id;
	int key;
}c[100010];


int key;

bool cmp( const corner &a, const corner &b ) {
	return a.x<b.x || a.x==b.x && ( a.y<b.y || a.y==b.y && (a.key&key) < (b.key&key) );
}

void doit( int n ) {
	int i, count = 0;
	bool inner = false;

	std::sort( c, c+n*4, cmp );

	for( i=0; i<4*n; i++ ) {
		if( c[i].key & key ) {
			if( inner )
				sign[ c[i].id ] = true;
			count--;
			if( count == 0 )
				inner = false;
		}
		else {
			if( count ) {
				sign[ c[i].id ] = true;
				inner = true;
			}
			count++;
		}
	}
}



int main( ) {
	int i, t, n;
	
	scanf( "%d", &n );

	for( i=0; i<n; i++ ) {
		scanf( "%d%d", &c[i*4].x, &c[i*4].y );
		scanf( "%d%d", &c[i*4+3].x, &c[i*4+3].y );

		c[i*4+1].x = c[i*4].x;
		c[i*4+1].y = c[i*4+3].y;

		c[i*4+2].x = c[i*4+3].x;
		c[i*4+2].y = c[i*4].y;
	}

	for( i=0; i<4*n; i++ ) {
		c[i].id = i>>2;
		c[i].key = i&3;
	}

	key = 1;
	doit( n );

	for( i=0; i<4*n; i++ ) {
		t = c[i].x;
		c[i].x = c[i].y;
		c[i].y = t;
	}

	key = 2;
	doit( n );

	int ans = 0;
	for( i=0; i<n; i++ )
		if( !sign[i] )
			ans++;

	printf( "%d\n", ans );

	return 0;
}