Cod sursa(job #846374)

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

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

const int dim = 50005;
int N, XC, YC;
bitset <dim> viz;
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 rez1 ()
{
	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 inclus (punct a, punct b) //return 1 daca b elte intre 0 si a
{
	if (b.x < 0)
	{
		a.x = -a.x;
		b.x = -b.x;
	}
	if (b.y < 0)
	{
		a.y = -a.y;
		b.y = -b.y;
	}
	return (a.x >= 0 && a.y >= 0 && a.x <= b.x && a.y <= b.y);
}

void rez2 ()
{
	int i, j;
	for (i = 1; i <= N; i++)
		viz[i] = 0;
	for (i = 1; i <= N; i++)
	{
		for (j = 1; j <= N; j++)
		{
			if (i == j)
				continue;
			if (inclus (P[i], P[j]))
				viz[i] = 1;
		}
	}
}

void afi2 ()
{
	int r = 0;
	for (int i = 1; i <= N; i++)
		if (viz[i] == 0)
			r++;
	fo << r << '\n';
}

int main ()
{
	cit ();
	rez1 ();
	/*rez2 ();
	afi2 ();	*/
	return 0;
}