2859.txt

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

Problem Id:2859  User Id:fzk 
Memory:3968K  Time:3060MS
Language:C++  Result:Accepted

Source 

#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( "%d\n", ans );
}

int main( ) {
	input( );
	doit( );
	return 0;
}