Pagini recente » Pokemon2 | Cod sursa (job #956345) | Cod sursa (job #3202314) | Cod sursa (job #3202340) | Cod sursa (job #8484)
Cod sursa(job #8484)
#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMAX 50500
#define min(a, b) ((a) < (b) ? (a):(b))
#define HMAX (1<<16)
#define INF 2000000001
using namespace std;
int N, X, Y, Num, H[NMAX], L, Pred[NMAX], T[NMAX];
vector<pair<int, int> > Cadran[4];
int search(int c, int x)
{
int mij, p1, p2, p = 0;
for (p1 = 0, p2 = L, mij = (p1+p2)/2; p1 <= p2; mij = (p1+p2)/2)
{
if (Cadran[c][ H[mij] ].second > x) p2 = mij-1;
else p1 = mij+1, p = mij;
}
return p;
}
int main()
{
int i, x, y, j, p;
freopen("pachete.in", "r", stdin);
scanf("%d %d %d", &N, &X, &Y);
for (i = 0; i < N; i++)
{
scanf("%d %d", &x, &y);
x -= X; y -= Y;
if (x >= 0 && y >= 0) Cadran[0].push_back(make_pair(abs(x), abs(y)));
if (x >= 0 && y < 0) Cadran[1].push_back(make_pair(abs(x), abs(y)));
if (x < 0 && y < 0) Cadran[2].push_back(make_pair(abs(x), abs(y)));
if (x < 0 && y >= 0) Cadran[3].push_back(make_pair(abs(x), abs(y)));
}
for (i = 0; i < 4; i++)
{
sort(Cadran[i].begin(), Cadran[i].end());
for (j = 1; j < NMAX; j++) H[j] = INF;
H[1] = 0; N = Cadran[i].size();
if (N > 0) Num++;
L = 1;
for (j = 1; j < N; j++)
{
p = search(i, Cadran[i][j].second);
Pred[j] = H[p];
if (H[p+1] < INF)
H[p+1] = ((Cadran[i][ H[p+1] ].second > Cadran[i][j].second) ? j:H[p+1]);
else L++, H[p+1] = j;
}
for (i = 1; i < N; i++)
T[ Pred[i] ]++;
for (i = 0; i < N; i++)
Num += (T[i]>1);
}
freopen("pachete.out", "w", stdout);
printf("%d\n", Num);
return 0;
}