Pagini recente » Cod sursa (job #246437) | Cod sursa (job #2440650) | Cod sursa (job #2655936) | Cod sursa (job #1263756) | Cod sursa (job #6660)
Cod sursa(job #6660)
#include <stdio.h>
#include <algorithm>
#define change(a, b) ( (a) ^= (b) ^= (a) ^= (b) )
#define NMax 50024
typedef struct { int x, y; } entry;
using namespace std;
int N, Ox, Oy;
entry v[NMax];
int C[4][NMax], h[4], last[NMax], nr_s, cnt = 0;
int cmp(entry A, entry B)
{ return A.x < B.x; }
int cadran(int x, int y)
{
if (x > 0 && y > 0) return 0;
if (x < 0 && y > 0) return 1;
if (x < 0 && y < 0) return 2;
return 3;
}
int main(void)
{
int i, r, li, ho, m, u;
freopen("pachete.in", "r", stdin);
freopen("pachete.out", "w", stdout);
for (scanf("%d %d %d", &N, &Ox, &Oy), i = 0; i < N; i++)
scanf("%d %d", &v[i].x, &v[i].y);
sort(v+0, v+N, cmp);
for (i = 0; i < N; i++)
{
r = cadran(v[i].x - Ox, v[i].y - Oy);
if (r == 0 || r == 1)
C[r][++h[r]] = v[i].y - Oy;
else C[r][++h[r]] = Oy - v[i].y;
}
for (r = 1; r <= 2; r++)
for (i = 1; i <= h[r]/2; i++)
change(C[r][i], C[r][h[r]-i+1]);
for (r = 0; r < 4; r++)
{
if (h[r] == 0) continue;
last[nr_s = 1] = C[r][1];
for (i = 2; i <= h[r]; i++)
{
li = 1; ho = nr_s; u = nr_s+1;
while (li <= ho)
{
m = ((li + ho) >> 1);
if (last[m] <= C[r][i]) u = m, ho = m-1;
else li = m+1;
}
last[u] = C[r][i];
if (u > nr_s) nr_s = u;
}
cnt += nr_s;
}
printf("%d\n", cnt);
return 0;
}