Cod sursa(job #8344)

Utilizator wefgefAndrei Grigorean wefgef Data 24 ianuarie 2007 17:35:07
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define punct pair<int, int>
#define pb push_back
#define sz size()

#define Nmax 50005

int n, rez, c1, c2;
vector< punct > v[4];
int list[2*Nmax+1];
#define list (list + Nmax)

void readdata()
{
	freopen("pachete.in", "r", stdin);
	freopen("pachete.out", "w", stdout);
	
	int X, Y, i, a, b;
	scanf("%d", &n);
	scanf("%d %d", &X, &Y);
	for (i = 0; i < n; ++i)
	{
		scanf("%d %d", &a, &b);
		if (a > X && b > Y) v[0].pb( mp(a, b) ); else
		if (a > X && b < Y) v[1].pb( mp(a, Y-b) ); else
		if (a < X && b < Y) v[2].pb( mp(X-a, Y-b) ); else
		v[3].pb( mp(X-a, b) );
	}
}

void cauta(int i, int j)
{
	int st = c1, dr = c2, m;
	while (st < dr)
	{
		m = (st+dr+1)/2;
		if (v[i][list[m]].y < v[i][j].y) st = m;
		else dr = m-1;
	}
	if (st >= c2)
	{
		list[++c2] =  j;
		return;
	}
	if (st == c1 && v[i][list[st]].y > v[i][j].y)
	{
		list[--c1] = j;
		return;
	}
	list[st] = j;
}

void solve()
{
	int i, j, val;
	
	for (i = 0; i < 4; ++i)
	{
		c1 = 1;
		c2 = 0;
		sort(v[i].begin(), v[i].end());
		for (j = 0; j < v[i].sz; ++j)
			cauta(i, j);
		rez += c2-c1+1;
	}
	printf("%d\n", rez);
}

int main()
{
	readdata();
	solve();
	return 0;
}