Cod sursa(job #846431)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 2 ianuarie 2013 10:12:16
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdlib.h>
using namespace std;

ifstream fi ("pachete.in");
ofstream fo ("pachete.out");

const int dim = 50005;
int N;
long long L[dim], XC, YC;
struct punct { long long x, y; } P[dim];
vector <punct> LP[4];

void cit ()
{
	fi >> N >> XC >> YC;
	for (int i = 1, gr; i <= N; i++)
	{
		fi >> P[i].x >> P[i].y;
		P[i].x -= XC;
		P[i].y -= YC;
		
		if (P[i].x >= 0 && P[i].y >= 0) gr = 0;
		if (P[i].x >  0 && P[i].y <  0) gr = 1;
		if (P[i].x <  0 && P[i].y >  0) gr = 2;
		if (P[i].x <= 0 && P[i].y <= 0) gr = 3;
		
		P[i].x = abs (P[i].x);
		P[i].y = abs (P[i].y);
		LP[gr].push_back (P[i]);
	}	
}

int cmp (punct a, punct b)
{
	if (a.x == b.x)
		return a.y < b.y;
	return a.x < b.x;
}

int cauta (long long V[], long long val)
{
	int p = 1, u = V[0], m;
	while (p <= u)
	{
		m = ((u - p) >> 1) + p;
		if (val < V[m])
			p = m + 1;
		else
			u = m - 1;
	}
	return p;
}

void rez ()
{
	int gr, i, r = 0, p;
	for (gr = 0; gr < 4; gr++)
	{
		sort (LP[gr].begin(), LP[gr].end(), cmp);
		L[0] = 0;
		for (i = 0; i < LP[gr].size(); i++)
		{
			p = cauta (L, LP[gr][i].y);
			if (p == L[0] + 1)
				L[++L[0]] = LP[gr][i].y;
			else
				L[p] = LP[gr][i].y;
		}
		r += L[0];
	}
	fo << r << '\n';
}

int main ()
{
	cit ();
	rez ();
	return 0;
}