Pagini recente » Cod sursa (job #875757) | Cod sursa (job #1834657) | Cod sursa (job #2217736) | Cod sursa (job #2177691) | Cod sursa (job #8259)
Cod sursa(job #8259)
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define FIN "pachete.in"
#define FOUT "pachete.out"
#define MAXN 50001
#define ul unsigned long
#define dist(i,j) (abs(X[i] - X[j]) + abs(Y[i] - Y[j]))
typedef struct { int x, y; } coord;
int dx[]={ 1, 1,-1,-1},
dy[]={ 1,-1,-1, 1};
int n, grad[4];
coord Dest[4][MAXN], src;
int Drum_UltY[MAXN];
bool operator<(const coord &A, const coord &B) {
return A.x < B.x;
}
void citire()
{
int i, c;
coord pct;
freopen(FIN, "r", stdin);
freopen(FOUT,"w",stdout);
scanf("%d\n%d %d", &n, &src.x, &src.y);
for (i=1; i<=n; ++i) {
scanf("%d %d", &pct.x, &pct.y);
pct.x -= src.x; pct.y -= src.y;
c = (pct.x < 0) ^ (pct.y < 0);
if (pct.x < 0) c += 2, pct.x = -pct.x;
if (pct.y < 0) pct.y = -pct.y;
Dest[c][ grad[c] ++ ] = pct;
}
}
int bcaut_desc(int l, int r, int val) {
int i, step, N = r-l;
for (step=1; step < N; step <<= 1) ;
for (i=N; step; step >>= 1)
if (i-step >= 0 && Drum_UltY[l + (i-step)] <= val)
i -= step;
return l + i;
}
void rez()
{
int i, j, poz, drumuri, dr_total = 0;
for (i=0; i<4; ++i) { // incearca toate cadranele...
if (!grad[i]) continue;
std::sort(Dest[i], Dest[i] + grad[i]);
Drum_UltY[(drumuri = 0) ++ ] = Dest[i][0].y;
for (j=1; j < grad[i]; ++j) {
// caut cel mai din dreapta drum in Drum_UltY cu Y<=Dest[i][j].y
poz = bcaut_desc(0, drumuri, Dest[i][j].y);
if (poz == drumuri) ++drumuri;
Drum_UltY[poz] = Dest[i][j].y;
}
dr_total += drumuri;
}
printf("%d\n", dr_total);
}
int main()
{
citire();
rez();
return 0;
}