Cod sursa(job #819770)

Utilizator ChallengeMurtaza Alexandru Challenge Data 19 noiembrie 2012 18:05:58
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const char InFile[]="pachete.in";
const char OutFile[]="pachete.out";
const int MaxN=50111;

ifstream fin(InFile);
ofstream fout(OutFile);

struct Point
{
	int x,y;

	inline bool operator< (const Point &A) const
	{
		if(x==A.x)
		{
			return y<A.y;
		}
		return x<A.x;
	}
};

int N,L[MaxN];
vector<Point> C[4];
Point O,P;

inline void Rotate(int ind)
{
	for(vector<Point>::iterator it=C[ind].begin();it!=C[ind].end();++it)
	{
		Point P=*it;
		it->x=P.y;
		it->y=-P.x;
	}
}

inline void Solve(int ind)
{
	sort(C[ind].begin(),C[ind].end());
	L[0]=0;
	for(vector<Point>::iterator it=C[ind].begin();it!=C[ind].end();++it)
	{
		int first=L[0];
		int step=1<<15;
		for(;step;step>>=1)
		{
			int index=first-step;
			if(index>0)
			{
				if(L[index]<it->y)
				{
					first=index;
				}
			}
		}
		if(first!=L[0])
		{
			L[++L[0]]=it->y;
		}
		else
		{
			L[first]=it->y;
		}
	}
}

int main()
{
	fin>>N;
	fin>>O.x>>O.y;
	for(register int i=1;i<=N;++i)
	{
		fin>>P.x>>P.y;
		P.x-=O.x;
		P.y-=O.y;
		if(P.x>0 && P.y>0)
		{
			C[0].push_back(P);
		}
		else if(P.x<0 && P.y>0)
		{
			C[1].push_back(P);
		}
		else if(P.x<0 && P.y>0)
		{
			C[2].push_back(P);
		}
		else
		{
			C[3].push_back(P);
		}
	}
	fin.close();

	int sol=0;
	for(register int i=0;i<4;++i)
	{
		for(register int j=0;j<i;++j)
		{
			Rotate(i);
		}
		Solve(i);
		sol+=L[0];
	}

	fout<<sol;
	fout.close();
	return 0;
}