Pagini recente » Cod sursa (job #2737841) | Cod sursa (job #1244075) | Cod sursa (job #1666220) | Cod sursa (job #2349424) | Cod sursa (job #8402)
Cod sursa(job #8402)
#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMAX 50500
#define max(a, b) ((a) > (b) ? (a):(b))
#define HMAX (1<<16)
#define INF 2000000001
using namespace std;
int N, X, Y, maxX, maxY, Num, H[2*HMAX];
vector<pair<int, int> > Cadran[4];
void update(int n, int x, int v)
{
int nod = HMAX+x;
H[nod] = x;
while (nod>1)
{
nod /= 2;
H[nod] = ((Cadran[n][ H[2*nod] ].second < Cadran[n][ H[2*nod+1] ].second) ? H[2*nod]:H[2*nod+1]);
}
}
int main()
{
int i, x, y, j;
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());
memset(H, 0, sizeof(H));
update(i, 0, Cadran[i][0].second);
if (Cadran[i].size() > 0) Num++;
for (j = 1; j < Cadran[i].size(); j++)
{
x = Cadran[i][j].first; y = Cadran[i][j].second;
if (Cadran[i][ H[1] ].second > y) Num++;
else
{
Cadran[i][ H[1] ].second = INF;
update(i, H[1], INF);
}
update(i, j, y);
}
}
freopen("pachete.out", "w", stdout);
printf("%d\n", Num);
return 0;
}