Cod sursa(job #2156598)

Utilizator ovidius11Stiriu Ovidius ovidius11 Data 8 martie 2018 20:45:24
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct point{
int x,y;
}p[5][50005];
int v[50005];
int u[5];
int cmp(point a,point b){
return a.x<b.x;}
int cmp2(point a,point b){
return a.x>b.x;}
int calc(int nr){
int num=1,i,st,dr,mij,last;
v[1]=p[nr][1].y;
for(i=2;i<=u[nr];i++){
st=1;
dr=num;
last=num+1;
while(st<=dr){
mij=(st+dr)/2;
if (v[mij]<p[nr][i].y){
last=mij;
dr=mij-1;}
else
st=mij+1;}
if (last==num+1)
num++;
v[last]=p[nr][i].y;}
return num;}
int calc2(int nr){
int num=1,i,st,dr,mij,last;
v[1]=p[nr][1].y;
for(i=2;i<=u[nr];i++){
st=1;
dr=num;
last=num+1;
while(st<=dr){
mij=(st+dr)/2;
if (v[mij]>p[nr][i].y){
last=mij;
dr=mij-1;}
else
st=mij+1;}
if (last==num+1)
num++;
v[last]=p[nr][i].y;}
return num;}
int main(){
freopen("pachete.in","r",stdin);
freopen("pachete.out","w",stdout);
int n,x,y,i,x1,y1,rasp=0;
scanf("%d%d%d",&n,&x,&y);
for(i=1;i<=n;i++){
scanf("%d%d",&x1,&y1);
if (x1>x && y1>y)
p[1][++u[1]].x=x1,p[1][u[1]].y=y1;
if (x1>x && y1<y)
p[2][++u[2]].x=x1,p[2][u[2]].y=y1;
if (x1<x && y1<y)
p[3][++u[3]].x=x1,p[3][u[3]].y=y1;
if (x1<x && y1>y)
p[4][++u[4]].x=x1,p[4][u[4]].y=y1;}
sort(p[1]+1,p[1]+u[1]+1,cmp);
sort(p[2]+1,p[2]+u[2]+1,cmp);
sort(p[3]+1,p[3]+u[3]+1,cmp2);
sort(p[4]+1,p[4]+u[4]+1,cmp2);
if (u[1])
rasp=rasp+calc(1);
if (u[2])
rasp=rasp+calc2(2);
if (u[3])
rasp=rasp+calc2(3);
if (u[4])
rasp=rasp+calc(4);
printf("%d\n",rasp);
return 0;}