# Poj Solution 3168

```http://poj.org/problem?id=3168

#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;

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( "%dn", ans );

return 0;
}
```
This entry was posted in poj. Bookmark the permalink.