Pagini recente » Cod sursa (job #64621) | Cod sursa (job #17203) | Cod sursa (job #122111) | Cod sursa (job #2875519) | Cod sursa (job #14266)
Cod sursa(job #14266)
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define NMAX 50001
using namespace std;
struct per { int x, y; } A[NMAX];
int St[NMAX];
int i, N, X, Y, Nr, Sol, K;
bool operator < (const per &a, const per &b)
{
return (a.x < b.x);
}
int BS1 (int elem, int st, int dr)
{
int l = st;
int r = dr;
int c = 0, pz = dr + 1;
while (l <= r)
{
c = (l + r)/2;
if (St[c] > elem) l = c + 1;
else pz = c, r = c - 1;
}
return pz;
}
int BS2 (int elem, int st, int dr)
{
int l = st;
int r = dr;
int c = 0, pz = dr + 1;
while (l <= r)
{
c = (l + r)/2;
if (St[c] < elem) l = c + 1;
else pz = c, r = c - 1;
}
return pz;
}
void op()
{
Sol += Nr, Nr = 0;
}
int main()
{
freopen("pachete.in", "r", stdin);
freopen("pachete.out", "w", stdout);
scanf("%d %d %d\n", &N, &X, &Y);
for (i= 1; i <= N; i++) scanf("%d %d", &A[i].x, &A[i].y);
sort(A + 1, A + N + 1);
for (i = 1; i <= N; i++)
if (A[i].x >= X && A[i].y >= Y)
{
K = BS1(A[i].y, 0, Nr - 1);
St[K] = A[i].y;
if (K == Nr) Nr++;
}
op();
for (i = N; i > 0; i--)
if (A[i].x <= X && A[i].y >= Y)
{
K = BS1(A[i].y, 0, Nr - 1);
St[K] = A[i].y;
if (K == Nr) Nr++;
}
op();
for (i = N; i > 0; i--)
if (A[i].x <= X && A[i].y <= Y)
{
K = BS2(A[i].y, 0, Nr - 1);
St[K] = A[i].y;
if (K == Nr) Nr++;
}
op();
for (i = 1; i <= N; i++)
if (A[i].x >= X && A[i].y <= Y)
{
K = BS2(A[i].y, 0, Nr - 1);
St[K] = A[i].y;
if (K == Nr) Nr++;
}
op();
printf("%d\n", Sol);
return 0;
}