Cod sursa(job #2148327)

Utilizator shantih1Alex S Hill shantih1 Data 1 martie 2018 17:35:45
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("pachete.in");
ofstream fout("pachete.out");

int l,i,j,nr,sx,sy,n[5],ns,ss[50005],st,dr,mid,rez,cdr;
struct pos
{	int x,y; }c[50005],cd[5][50005],p;

bool cmp(pos x,pos y)
{
	if(x.x==y.x)	return x.y<y.y;
	if(cdr==2||cdr==4)	return x.x>y.x;
	return x.x<y.x;
}
void cadran(int cdr)
{
	l=n[cdr];
	for(i=0;i<=l;i++)
	{
		c[i]=cd[cdr][i];
		ss[i]=0;
	}
	sort(c+1,c+l+1,cmp);
	
	ns=1;
	ss[1]=c[1].y;
	for(i=2;i<=l;i++)
	{
		nr=c[i].y;
		st=1;	dr=ns;
		while(st<=dr)
		{
			mid=st+(dr-st)/2;
			if(ss[mid]<nr)	 dr=mid-1;
			else			 st=mid+1;
		}
		if(ss[mid]>nr)	mid++;
		
		if(nr<ss[ns])
		{	ns++;	ss[ns]=nr;	}
		else	ss[mid]=nr;
	}
	if(l<=1)	ns=l;
	rez+=ns;
}
int main() {
	
	fin>>l;
	fin>>sx>>sy;
	for(i=1;i<=l;i++)
	{
		fin>>p.x>>p.y;
		if(p.x>sx&&p.y>sy)
		{	n[1]++;	cd[1][n[1]]=p;	}
		if(p.x<sx&&p.y>sy)
		{	n[2]++;	cd[2][n[2]]=p;	}
		if(p.x<sx&&p.y<sy)
		{ 	n[3]++;	cd[3][n[3]]=p;	}
		if(p.x>sx&&p.y<sy)
		{	n[4]++;	cd[4][n[4]]=p;	}
	}
	
	for(sx=1;sx<=4;sx++)	cadran(sx);
	fout<<rez<<"\n";
}