Pagini recente » Cod sursa (job #2045247) | Cod sursa (job #1951340) | Cod sursa (job #105566) | Cod sursa (job #3648) | Cod sursa (job #381279)
Cod sursa(job #381279)
#include <algorithm>
#include <stdio.h>
#include <vector>
#define MAX 50010
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std;
vector <pair <int, int> > cadr[8];
int n, Ox, Oy, loc, poz, tot;
int vctX[MAX], vctY[MAX], vctAlt[MAX];
inline void cauta(int fr, int ls, int pus)
{
if (fr > ls)
return;
int med = (fr + ls) / 2;
if (vctAlt[med] < pus && vctAlt[med - 1] > pus)
loc = med;
else if (vctAlt[med] < pus)
cauta(fr, med - 1, pus);
else cauta(med + 1, ls, pus);
}
int main()
{
freopen("pachete.in", "r", stdin);
freopen("pachete.out", "w", stdout);
scanf("%d", &n);
scanf("%d %d", &Ox, &Oy);
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &vctX[i], &vctY[i]);
vctX[i] -= Ox;
vctY[i] -= Oy;
}
for (int i = 1; i <= n; i++)
{
if (vctX[i] > 0 && vctY[i] > 0)
cadr[1].pb(mp(vctX[i], vctY[i]));
if (vctX[i] < 0 && vctY[i] > 0)
cadr[2].pb(mp(-vctX[i], vctY[i]));
if (vctX[i] < 0 && vctY[i] < 0)
cadr[3].pb(mp(-vctX[i], -vctY[i]));
if (vctX[i] > 0 && vctY[i] < 0)
cadr[4].pb(mp(vctX[i], -vctY[i]));
}
for (int c = 1; c <= 4; c++)
{
vector <pair <int, int> > vctAct = cadr[c];
sort(vctAct.begin(), vctAct.end());
poz = 0;
memset(vctAlt, 0, sizeof(vctAlt));
vctAlt[0] = LONG_MAX;
for (int i = 0; i < vctAct.size(); i++)
{
loc = poz + 1;
cauta(1, poz, vctAct[i].s);
vctAlt[loc] = vctAct[i].s;
if (loc == poz + 1)
++poz;
}
tot += poz;
}
printf("%d\n", tot);
fclose(stdin);
fclose(stdout);
return 0;
}