Cod sursa(job #846376)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 1 ianuarie 2013 23:18:07
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <stack>
using namespace std;

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

const int dim = 50005;
int N, 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;
}

void rez ()
{
	int gr, i, r = 0;
	stack <punct> L;
	for (gr = 0; gr < 4; gr++)
	{
		sort (LP[gr].begin(), LP[gr].end(), cmp);
		while (!L.empty()) L.pop ();
		for (i = 0; i < LP[gr].size(); i++)
		{
			while (L.size() > 0 && L.top().y <= LP[gr][i].y)
				L.pop ();
			L.push (LP[gr][i]);
		}
		r += L.size();
	}
	fo << r << '\n';
}

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