Pagini recente » Cod sursa (job #2597095) | Cod sursa (job #1633845) | Cod sursa (job #1983769) | Cod sursa (job #845239) | Cod sursa (job #8508)
Cod sursa(job #8508)
#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], D[NMAX], F[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 = 0; j < NMAX; j++) H[j] = INF, D[i] = F[i] = Pred[i] = 0;
H[0] = 0;
H[1] = 0; N = Cadran[i].size();
D[0] = 1;
L = 1;
for (j = 1; j < N; j++)
{
p = search(i, Cadran[i][j].second);
Pred[j] = H[p];
D[j] = p+1;
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;
}
if (N > 0)
{
for (j = N-1; j >= 0; j--)
if (F[j]==0)
{
p = j;
while (Pred[p] != p) F[p] = 1, p = Pred[p];
F[p] = 1;
Num++;
}
}
}
freopen("pachete.out", "w", stdout);
printf("%d\n", Num);
return 0;
}