Pagini recente » Cod sursa (job #1364382) | Cod sursa (job #3264045) | Cod sursa (job #2694839) | Cod sursa (job #2309630) | Cod sursa (job #14205)
Cod sursa(job #14205)
#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 = 0;
memset(sir, -1, 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;
}
int cmpy(const pair<int, int> a, const pair<int, int> b)
{
if (a.y <= b.y)
if (a.y < b.y)
return 1;
else if (a.x > b.x)
return 1;
return 0;
}
void solve()
{
int m, i;
sort(punct+1, punct+n+1);
// cadran 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 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 + m + 1);
solve2(m);
// cadran 2
m = 0;
sort(punct+1, punct+n+1, cmpy);
for (i=1; i<=n; ++i)
if (punct[i].x < 0 && punct[i].y >= 0)
s[++m] = -punct[i].x;
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].x;
reverse(s + 1, s + m + 1);
solve2(m);
printf("%d\n", sol);
}
int main()
{
freopen("pachete.in", "r", stdin);
freopen("pachete.out", "w", stdout);
citire();
solve();
return 0;
}