Cod sursa(job #2147751)

Utilizator shantih1Alex S Hill shantih1 Data 28 februarie 2018 22:57:43
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("pachete.in");
ofstream fout("pachete.out");

int n,i,j,nr,sx,sy,n1,n2,n3,n4,ns,ss[50005],st,dr,mid,rez;
struct pos
{	int x,y; }c[50005],c1[50005],c2[50005],c3[50005],c4[50005],p;
bool cmp(pos x,pos y)
{
	if(x.x==y.x)	return x.y<y.y;
	return x.x<y.x;
}
void cadran()
{
	sort(c+1,c+n+1,cmp);
	ns=1;
	ss[1]=c[1].y;
	for(i=2;i<=n;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(n==0)	ns=0;
	rez+=ns;
}

int main() {
	
	fin>>n;
	fin>>sx>>sy;
	for(i=1;i<=n;i++)
	{
		fin>>p.x>>p.y;
		if(p.x>=sx&&p.y>=sy)
		{	n1++;	c1[n1]=p;	}
		else if(p.x>=sx)
		{	n2++;	c2[n2]=p;	}
		else if(p.y<=sy)
		{ 	n3++;	c3[n3]=p;	}
		else
		{	n4++;	c4[n4]=p;	}
	}
	
	n=n1;
	for(i=1;i<=n1;i++)	c[i]=c1[i];
	cadran();
	n=n2;
	for(i=1;i<=n2;i++)	c[i]=c2[i];
	cadran();
	n=n3;
	for(i=1;i<=n3;i++)	c[i]=c3[i];
	cadran();
	n=n4;
	for(i=1;i<=n4;i++)	c[i]=c4[i];
	cadran();

	fout<<rez<<"\n";
}