Pagini recente » Cod sursa (job #741070) | Cod sursa (job #1698632) | Cod sursa (job #1881583) | Cod sursa (job #854021) | Cod sursa (job #1252318)
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("pachete.in");
ofstream fout("pachete.out");
#define NMAX 50005
struct punct
{
int x,y;
} aux,A[5][NMAX];
int n,k,x,y,x0,y0,cd,sol,a[5],v[NMAX];
int cadran(int x, int y)
{
if (x>0)
{
if (y>0) return 1;
else return 4;
}
else
{
if (y>0) return 2;
else return 3;
}
}
bool cmp(const punct &A, const punct &B)
{
if (A.x==B.x) return (A.y<B.y);
return (A.x<B.x);
}
int main()
{
int i,j,st,dr,mij;
fin>>n>>x0>>y0;
for (i=1;i<=n;++i)
{
fin>>x>>y;
x-=x0, y-=y0;
aux.x=abs(x), aux.y=abs(y);
cd=cadran(x,y);
A[cd][++a[cd]]=aux;
}
for (i=1;i<5;++i)
sort(A[i]+1,A[i]+a[i]+1,cmp);
for (j=1;j<5;++j)
{
if (!a[j]) continue;
v[k=1]=1;
for (i=2;i<=a[j];++i)
{
if (A[j][i].y<A[j][v[k]].y)
{
v[++k]=i;
continue;
}
st=1, dr=k;
while (st<=dr)
{
mij=(st+dr)>>1;
if (A[j][i].y<A[j][v[mij]].y)
dr=mij-1;
else
st=mij+1;
}
v[dr]=i;
}
sol+=k;
}
fout<<sol<<"\n";
return 0;
}