Pagini recente » Cod sursa (job #2746319) | Cod sursa (job #2947179) | Cod sursa (job #1875156) | Cod sursa (job #1069706) | Cod sursa (job #8494)
Cod sursa(job #8494)
#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];
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, D[i] = 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);
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 = 0; j < N; j++) if (D[j] >= D[j+1]) Num++;
}
freopen("pachete.out", "w", stdout);
printf("%d\n", Num);
return 0;
}