Pagini recente » Cod sursa (job #3270766) | Cod sursa (job #2669827) | Cod sursa (job #2281048) | Cod sursa (job #2944401) | Cod sursa (job #2276770)
#include <fstream>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
FILE *fin=fopen("pachete.in","r");
ofstream fout("pachete.out");
int n,i,x0,y0,xi,yi,a,b,st,dr,mid,poz,x,drumuri;
bool ok;
pair <int,int> v1[50001],v2[50001],v3[50001],v4[50001];
int p1[50001];
int main()
{
fscanf(fin,"%d%d%d",&n,&x0,&y0);
for(i=1;i<=n;i++)
{
fscanf(fin,"%d%d",&xi,&yi);
a=xi-x0;
b=yi-y0;
if(a>=0 && b>=0)
{
v1[++v1[0].first].first=a;
v1[v1[0].first].second =b;
}
else if(a>=0 && b<0)
{
v2[++v2[0].first].first=a;
v2[v2[0].first].second =b;
}
else if(a<0 && b<0)
{
v3[++v3[0].first].first=a;
v3[v3[0].first].second =b;
}
else if(a<0 && b>=0)
{
v4[++v4[0].first].first=a;
v4[v4[0].first].second =b;
}
}
sort(v1+1,v1+v1[0].first+1);
sort(v2+1,v2+v2[0].first+1);
sort(v3+1,v3+v3[0].first+1);
sort(v4+1,v4+v4[0].first+1);
/// /////////// CAD 1
if(v1[0].first>0)
{
p1[++p1[0]]=v1[1].second;
for(i=2; i<=v1[0].first; i++)
{
p1[p1[0]+1]=-1;
st=0;dr=p1[0];
x=v1[i].second;
poz=-1;
while(st<=dr)
{
mid=(st+dr)/2;
if(p1[mid]<=x && p1[mid-1]>x)
{
poz=mid; break;
}
else if(p1[mid]>x)
st=mid+1;
else {poz=mid;dr=mid-1;}
}
if(poz>-1)
{///cel mai mare elem mai mic sau egal cu x este pe pozitia poz; continuam drumul
p1[poz]=x;
}
else
{///drum nou
p1[p1[0]+1]=x;
drumuri++;
}
}
}
fout<<drumuri;
return 0;
}