Pagini recente » Cod sursa (job #168872) | Cod sursa (job #2687502) | Cod sursa (job #192668) | Cod sursa (job #261828) | Cod sursa (job #14174)
Cod sursa(job #14174)
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
#define Nmax 50005
#define x first
#define y second
int n, x0, y0, sol;
pair<int, int> punct[Nmax];
int s[Nmax], sir[Nmax];
void citire()
{
int i;
scanf("%d\n", &n);
scanf("%d %d\n", &x0, &y0);
for (i=1; i<=n; ++i)
{
scanf("%d %d\n", &punct[i].x, &punct[i].y);
punct[i].x -= x0;
punct[i].y -= y0;
}
}
void solve2(int n)
{
int i, st, dr, mij, l = 0, ind;
memset(sir, 0, sizeof(sir));
for (i=1; i<=n; ++i)
{
st = 1;
dr = l + 1;
while (st <= dr)
{
mij = (st + dr) / 2;
if (sir[mij] <= s[i])
{
ind = mij;
dr = mij - 1;
}
else
st = mij + 1;
}
sir[ind] = s[i];
if (ind > l)
l = ind;
}
sol += l;
}
void solve()
{
int m, i;
// cadran 1
sort(punct+1, punct+n+1);
m = 0;
for (i=1; i<=n; ++i)
if (punct[i].x > 0 && punct[i].y >= 0)
s[++m] = punct[i].y;
solve2(m);
// cadran 4
m = 0;
for (i=1; i<=n; ++i)
if (punct[i].x >= 0 && punct[i].y < 0)
s[++m] = -punct[i].y;
solve2(m);
// cadran 2
m = 0;
for (i=1; i<=n; ++i)
if (punct[i].x <= 0 && punct[i].y > 0)
s[++m] = punct[i].y;
reverse(s + 1, s + n + 1);
solve2(m);
// cadran 3
m = 0;
for (i=1; i<=n; ++i)
if (punct[i].x < 0 && punct[i].y <= 0)
s[++m] = -punct[i].y;
reverse(s + 1, s + n + 1);
solve2(m);
printf("%d\n", sol);
}
int main()
{
freopen("pachete.in", "r", stdin);
freopen("pachete.out", "w", stdout);
citire();
solve();
return 0;
}