Cod sursa(job #845802)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 31 decembrie 2012 15:53:49
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <bitset>
using namespace std;

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

const int dim = 50005;
int N, XC, YC, south;
bitset <dim> viz;
struct punct { long long x, y; int i; } P[dim];

void cit ()
{
	fi >> N >> XC >> YC;
	south = 1;
	for (int i = 1; i <= N; i++)
	{
		fi >> P[i].x >> P[i].y;
		P[i].x -= XC;
		P[i].y -= YC;
		P[i].i = i;
		if (P[south].y > P[i].y || (P[south].y == P[i].y && P[south].x > P[i].x))
			south = i;
	}	
}

int cmp (punct a, punct b)
{
	if (a.i == south)
		return 1;
	if (b.i == south)
		return 0;
	return a.x * b.y - b.x * a.y > 0;
}

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 parc_st ()
{
	int i, pa = 1;
	for (i = 2; i <= N; i++)
	{
		if (inclus (P[i], P[pa]))
			viz[i] = 1;
		else
			pa = i;
	}
}

void parc_dr ()
{
	int i, pa = 1;
	for (i = N; i >= 2; i--)
	{
		if (inclus (P[i], P[pa]))
			viz[i] = 1;
		else
			pa = i;
	}
}


void rez1 ()
{
	sort (P+1, P+1+N, cmp);
	parc_st ();
	parc_dr ();
}

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 afi ()
{
	int r = 0;
	for (int i = 1; i <= N; i++)
		if (viz[i] == 0)
			r++;
	fo << r << '\n';
}

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