Cod sursa(job #1938987)
Utilizator | Data | 25 martie 2017 13:05:52 | |
---|---|---|---|
Problema | Pachete | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 3.95 kb |
#include<algorithm>
#include<cstdio>
using namespace std;
struct pachete
{
int x,y;
};
pachete v[50001];
bool sortare(pachete a,pachete b)
{
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
int drumurisd[50001],drumurijd[50001],drumurijs[50001],drumuriss[50001];
int main()
{
freopen("pachete.in","r",stdin);
freopen("pachete.out","w",stdout);
int n,xs,ys,i,nrdrumurisd,nrdrumurijd,nrdrumurijs,nrdrumuriss,l1,l2,mij,f;
nrdrumurijd=nrdrumurijs=nrdrumurisd=nrdrumuriss=0;
scanf("%d%d%d",&n,&xs,&ys);
for(i=1;i<=n;i++)
{
scanf("%d%d",&v[i].x,&v[i].y);
}
sort(v+1,v+n+1,sortare);
for(i=1;i<=n;i++)
{
if(v[i].x>xs&&v[i].y>ys)//CADRANUL SUS-DREAPTA
{
if(nrdrumurisd==0)
{
drumurisd[++nrdrumurisd]=v[i].y;
}
else
{
l1=1;
l2=nrdrumurisd;
f=-1;
while(l1<=l2)
{
mij=(l1+l2)/2;
if(drumurisd[mij]<v[i].y)
{
l1=mij+1;
f=mij;
}
else
{
l2=mij-1;
}
}
drumurisd[f]=v[i].y;
if(f==-1)
drumurisd[++nrdrumurisd]=v[i].y;
}
}
if(v[i].x>xs&&v[i].y<ys)//CADRANUL JOS-DREAPTA
{
if(nrdrumurijd==0)
{
drumurijd[++nrdrumurijd]=v[i].y;
}
else
{
l1=1;
l2=nrdrumurijd;
f=-1;
while(l1<=l2)
{
mij=(l1+l2)/2;
if(drumurijd[mij]>v[i].y)
{
l1=mij+1;
f=mij;
}
else
{
l2=mij-1;
}
}
if(f==-1)
drumurijd[++nrdrumurijd]=v[i].y;
else
drumurijd[f]=v[i].y;
}
}
if(v[i].x<xs&&v[i].y<ys)//CADRANUL JOS-STANGA
{
if(nrdrumurijs==0)
{
drumurijs[++nrdrumurijs]=v[i].y;
}
else
{
l1=1;
l2=nrdrumurijs;
f=-1;
while(l1<=l2)
{
mij=(l1+l2)/2;
if(drumurijs[mij]>v[i].y)
{
l1=mij+1;
f=mij;
}
else
{
l2=mij-1;
}
}
drumurijs[f]=v[i].y;
if(f==-1)
drumurijs[++nrdrumurijs]=v[i].y;
}
}
if(v[i].x<xs&&v[i].y>ys)//CADRANUL SUS-STANGA
{
if(nrdrumuriss==0)
{
drumuriss[++nrdrumuriss]=v[i].y;
}
else
{
l1=1;
l2=nrdrumuriss;
f=-1;
while(l1<=l2)
{
mij=(l1+l2)/2;
if(drumuriss[mij]<v[i].y)
{
l1=mij+1;
f=mij;
}
else
{
l2=mij-1;
}
}
drumuriss[f]=v[i].y;
if(f==-1)
drumuriss[++nrdrumuriss]=v[i].y;
}
}
}
printf("%d",nrdrumurisd+nrdrumurijd+nrdrumurijs+nrdrumuriss);
return 0;
}