Cod sursa(job #381279)

Utilizator ProtomanAndrei Purice Protoman Data 9 ianuarie 2010 21:31:51
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <algorithm>
#include <stdio.h>
#include <vector>

#define MAX 50010
#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

vector <pair <int, int> > cadr[8];
int n, Ox, Oy, loc, poz, tot;
int vctX[MAX], vctY[MAX], vctAlt[MAX];

inline void cauta(int fr, int ls, int pus)
{
	if (fr > ls)
		return;

	int med = (fr + ls) / 2;
	if (vctAlt[med] < pus && vctAlt[med - 1] > pus)
		loc = med;
	else if (vctAlt[med] < pus)
		cauta(fr, med - 1, pus);
	else cauta(med + 1, ls, pus);
}

int main()
{
	freopen("pachete.in", "r", stdin);
	freopen("pachete.out", "w", stdout);

	scanf("%d", &n);

	scanf("%d %d", &Ox, &Oy);

	for (int i = 1; i <= n; i++)
	{
		scanf("%d %d", &vctX[i], &vctY[i]);

		vctX[i] -= Ox;
		vctY[i] -= Oy;
	}

	for (int i = 1; i <= n; i++)
	{
		if (vctX[i] > 0 && vctY[i] > 0)
			cadr[1].pb(mp(vctX[i], vctY[i]));
		if (vctX[i] < 0 && vctY[i] > 0)
			cadr[2].pb(mp(-vctX[i], vctY[i]));
		if (vctX[i] < 0 && vctY[i] < 0)
			cadr[3].pb(mp(-vctX[i], -vctY[i]));
		if (vctX[i] > 0 && vctY[i] < 0)
			cadr[4].pb(mp(vctX[i], -vctY[i]));
	}

	for (int c = 1; c <= 4; c++)
	{
		vector <pair <int, int> > vctAct = cadr[c];

		sort(vctAct.begin(), vctAct.end());

		poz = 0;
		memset(vctAlt, 0, sizeof(vctAlt));
		vctAlt[0] = LONG_MAX;

		for (int i = 0; i < vctAct.size(); i++)
		{
			loc = poz + 1;
			cauta(1, poz, vctAct[i].s);

			vctAlt[loc] = vctAct[i].s;
			if (loc == poz + 1)
				++poz;
		}

		tot += poz;
	}

	printf("%d\n", tot);

	fclose(stdin);
	fclose(stdout);
	return 0;
}