Pagini recente » Cod sursa (job #90973) | Borderou de evaluare (job #3201611) | Cod sursa (job #250607) | Cod sursa (job #3175378) | Cod sursa (job #2451455)
#include <fstream>
#include <iostream>
#include <climits>
#include <cstring>
using namespace std;
ifstream fin("tribute.in");
ofstream fout("tribute.out");
#define RANGE 50000
int d;
int spot[RANGE + 1];
int distLeft[RANGE + 1], distRight[RANGE + 1];
int solSpot, solDist;
#define DIST_LEFT(i) (((i) >= 0 && (i) <= RANGE) ? distLeft[i] : 0)
#define DIST_RIGHT(i) (((i) >= 0 && (i) <= RANGE) ? distRight[i] : 0)
void runRoutine();
int main() {
int n, dx, dy;
fin>>n>>dx>>dy;
int* vx = new int[RANGE + 1];
memset(vx, 0, sizeof(int) * (RANGE + 1));
int* vy = new int[RANGE + 1];
memset(vy, 0, sizeof(int) * (RANGE + 1));
for (int i = 0; i < n; i++) {
int x, y;
fin>>x>>y;
vx[x]++;
vy[y]++;
}
//initialize for x
d = dx;
memcpy(spot, vx, sizeof(int) * (RANGE + 1));
runRoutine();
int distX = solDist;
//cout<<"Spot: "<<solSpot<<"\nDist: "<<solDist<<'\n';
//initialize for y
d = dy;
memcpy(spot, vy, sizeof(int) * (RANGE + 1));
runRoutine();
int distY = solDist;
//cout<<"Spot: "<<solSpot<<"\nDist: "<<solDist<<'\n';
fout<<distX + distY<<'\n';
}
void runRoutine() {
//populate distLeft
for (int i = 0, prez = 0, accum = 0; i < RANGE + 1; i++) {
accum += prez;
distLeft[i] = accum;
if (spot[i]) prez+= spot[i];
}
//populate distRight
for (int i = RANGE, prez = 0, accum = 0; i >= 0; i--) {
accum += prez;
distRight[i] = accum;
if (spot[i]) prez+= spot[i];
}
//get min total
solSpot = -1, solDist = INT_MAX;
for (int i = 0; i < RANGE + 1; i++)
if (solDist > DIST_LEFT(i) + DIST_RIGHT(i + d)) {
solDist = DIST_LEFT(i) + DIST_RIGHT(i + d);
solSpot = i;
}
}