Pagini recente » Cod sursa (job #3317753) | Cod sursa (job #3350008) | Cod sursa (job #3335724) | Cod sursa (job #3326694) | Cod sursa (job #3323560)
#include <bits/stdc++.h>
using namespace std;
ifstream f("tribute.in");
ofstream g("tribute.out");
int n, dx, dy;
int ans_oriz = INT_MAX, ans_vert = INT_MAX;
int a, b, frx[50005], fry[50005], ma_x = INT_MIN, mi_x = INT_MAX, ma_y = INT_MIN, mi_y = INT_MAX;
void orizontala() {
if (ma_x - mi_x <= dx)
ans_oriz = 0;
else {
int sum_ant = 0, sum_post = 0, points_ant = 0, points_post = 0;
for (int i=mi_x; i<=ma_x; ++i) {
if (i > dx) {
points_post += frx[i];
sum_post += frx[i] * i;
}
}
ans_oriz = min (ans_oriz, sum_post - points_post * dx);
for (int i=1; i+dx <= ma_x; ++i) {
points_ant += frx[i-1];
sum_ant += frx[i-1] * (i-1);
points_post -= frx[i+dx];
sum_post -= frx[i+dx] * (i+dx);
int dist = points_ant * i - sum_ant + sum_post - points_post * (i+dx);
ans_oriz = min (ans_oriz, dist);
}
}
}
void verticala () {
if (ma_y - mi_y <= dy)
ans_vert = 0;
else {
int sum_ant = 0, sum_post = 0, points_ant = 0, points_post = 0;
for (int i=mi_y; i<=ma_y; ++i) {
if (i > dy) {
points_post += fry[i];
sum_post += fry[i] * i;
}
}
ans_vert = min (ans_vert, sum_post - points_post * dy);
for (int i=1; i+dy <= ma_y; ++i) {
points_ant += fry[i-1];
sum_ant += fry[i-1] * (i-1);
points_post -= fry[i+dy];
sum_post -= fry[i+dy] * (i+dy);
int dist = points_ant * i - sum_ant + sum_post - points_post * (i+dy);
ans_vert = min (ans_vert, dist);
}
}
}
int main()
{
f >> n >> dx >> dy;
for (int i=1; i<=n; ++i) {
f >> a >> b;
frx[a] ++;
fry[b] ++;
ma_x = max (ma_x, a);
mi_x = min (mi_x, a);
ma_y = max (ma_y, b);
mi_y = min (mi_y, b);
}
orizontala();
//cout << endl;
verticala();
g << ans_oriz + ans_vert;
return 0;
}