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.

Leave a Reply

Your email address will not be published. Required fields are marked *