Cod sursa(job #729797)

Utilizator fhandreiAndrei Hareza fhandrei Data 30 martie 2012 09:48:04
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
//Include
#include <fstream>
#include <set>
#include <utility>
#include <queue>
using namespace std;

//Definitii
#define punct pair<int, int>
#define pctIt multiset<punct>::iterator
#define x first
#define y second

//Functii
inline int det(punct a, punct b, punct c);

//Variabile
ifstream in("pachete.in");
ofstream out("pachete.out");

int n;
int drumuri;
punct start, curent;
multiset<punct> puncte;
pctIt it, end, startPoz;
queue<pctIt> eliminate;

//Main
int main()
{
	in >> n;
	in >> start.x >> start.y;
	puncte.insert(start);
	while(n--)
		in >> curent.x >> curent.y, puncte.insert(curent);
	
	startPoz = puncte.find(start);
	
	
	while(puncte.begin() != startPoz)
	{
		curent = *puncte.begin();
		puncte.erase(puncte.begin());
		for(it=puncte.begin() ; it!=startPoz ; ++it)
			if(!det(start, curent, *it))
				eliminate.push(it);
		
		while(!eliminate.empty())
			puncte.erase(eliminate.front()), eliminate.pop();
		
		++drumuri;
	}
	puncte.erase(startPoz);
	while(!puncte.empty())
	{
		curent = *puncte.begin();
		puncte.erase(puncte.begin());
		end = puncte.end();
		for(it=puncte.begin() ; it!=end ; ++it)
			if(!det(start, curent, *it))
				eliminate.push(it);
		
		while(!eliminate.empty())
			puncte.erase(eliminate.front()), eliminate.pop();
		
		++drumuri;
	}
	
	out << drumuri;
	
	in.close();
	out.close();
	return 0;
}

inline int det(punct a, punct b, punct c)
{	return (a.x*b.y + b.x*c.y + c.x*a.y - a.y*b.x - b.y*c.x - c.y*a.x);	}