Pagini recente » Cod sursa (job #1084675) | Cod sursa (job #92663) | Cod sursa (job #895352) | Cod sursa (job #2693894) | Cod sursa (job #67343)
Cod sursa(job #67343)
using namespace std;
#define MAX_N 50005
#include <stdio.h>
#include <fstream>
FILE *fin=fopen("pachete.in","r"),
*fout=fopen("pachete.out","w");
typedef struct
{
int x;
int y;
} point;
int s[MAX_N];
point p[MAX_N];
int n,m;
void read (void)
{
int i,x0,y0;
fscanf(fin,"%d",&n);
fscanf(fin,"%d %d",&x0,&y0);
for (i=1; i<=n ;i++){
fscanf(fin,"%d %d",&p[i].x,&p[i].y);
p[i].x-=x0; p[i].y-=y0;
}
}
void part(int st,int dr,int &stst,int &stdr,int &drst,int &drdr)
{
point aux;
int i,j,piv;
piv=p[(st+dr)/2].x; i=st-1; j=dr+1;
while (i<j)
{ do {i++;} while (piv>p[i].x); do {j--;} while (piv<p[j].x);
if (i<j) { aux=p[i]; p[i]=p[j]; p[j]=aux; } }
if (i==j) { stdr=j-1; drst=i+1; }
else { stdr=j; drst=i; }
stst=st; drdr=dr;
}
void sort(int st, int dr)
{ int stst,stdr,drst,drdr;
if (st<dr) { part(st,dr,stst,stdr,drst,drdr);
sort(stst,stdr); sort(drst,drdr); }
}
int find (int x)
{
int mj,li,lf;
li=1; lf=m;
if (x<s[m]) {m++; return m; };
while (li<=lf)
{
mj=(li+lf)/2;
if (s[mj]<x) lf=mj-1;
if (s[mj]>x) li=mj+1;
if (s[mj]==x) break;
}
return mj;
}
void solve()
{
int i,j;
sort(1,n);
for (i=1; i<=n; i++)
{
j=find(p[i].y); m=j;
s[j]=p[i].y;
}
fprintf(fout,"%d\n",m);
}
int main()
{
read();
solve();
fclose(fin);
fclose(fout);
return 0;
}