Poj Solution 2859

http://poj.org/problem?id=2859

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

typedef pair<int,int> point;
int n, a, b;
point p[500100];

void input( ) {
    int i;
    scanf( "%d", &n );
    scanf( "%d%d", &a, &b );
    for( i=0; i<n; i++ )
        scanf( "%d%d", &p[i].first, &p[i].second );
}



void doit( ) {
    int i, j, k, l, ans = 0;

    sort( p, p+n );

    p[n].first = p[n+1].first = p[n+2].first = 2000000010;
    p[n].second = -1000000010;
    p[n+1].second = 0;
    p[n+2].second =1000000010;

    for( i=0, j=0, k=0, l=0; l<n; i++ ) {
        if( p[i].first < p[j].first )
            i = j;
        while( p[j].first == p[i].first && p[j].second < p[i].second+b )
            j++;
        if( k <= j ) k = j+1;
        while( p[k].first < p[i].first+a 
            || ( p[k].first == p[i].first+a && p[k].second < p[i].second ) )
            k++;
        if( l <= k ) l = k+1;
        while( p[l].first == p[k].first && p[l].second < p[k].second+b )
            l++;
        if( p[i].first == p[j].first && p[j].second == p[i].second+b &&
            p[k].first == p[l].first && p[l].second == p[k].second+b &&
            p[i].first + a == p[k].first && p[i].second == p[k].second )
            ans++;
    }
    printf( "%dn", ans );
}

int main( ) {
    input( );
    doit( );
    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 *