Pagini recente » Cod sursa (job #2615511) | Cod sursa (job #2022056) | Cod sursa (job #1766095) | Cod sursa (job #302564) | Cod sursa (job #3233676)
#include <iostream>
#include <fstream>
#include <vector>
//#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("tribute.in");
ofstream fout("tribute.out");
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n, dx, dy; fin >> n >> dx >> dy;
vector <ll> x, y;
for(int i = 0; i < n; i++){
int l, r; fin >> l >> r;
x.push_back(l);
y.push_back(r);
}
sort(x.begin(), x.end());
sort(y.begin(), y.end());
ll sp[x.size() + 1];
sp[0] = 0;
for(int i = 0; i < n; i++){
sp[i + 1] = sp[i] + x[i];
}
/*cout << "x : ";
for(int i = 0; i < n; i++) cout << x[i] << " ";
cout << '\n';
cout << "sp : ";
for(int i = 0; i <= n; i++) cout << sp[i] << " ";
cout << '\n';*/
int i1 = 0, i2 = 0;
ll l = 0, r = dx;
ll mini = -1;
for(;r <= x.back(); l++, r++){
while(i2 < x.size() && x[i2] <= r) i2++;
while(i1 < x.size() && x[i1] < l) i1++;
//cout << "l = " << l << " r = " << r << " i1 = " << i1 << " i2 = " << i2;
ll sum = 0;
sum += l * i1 - sp[i1];
sum += (sp[n] - sp[i2]) - r * (n - i2);
//cout << " sum = " << sum << '\n';
//cout << " -- > l = " << l * i1 - sp[i1] << '\n';
//cout << " -- > r = " << (sp[n] - sp[i2]) - r * (n - i2) << '\n';
if(mini == -1 || sum < mini) mini = sum;
}
//cout << "minim pe OX : " << mini << '\n';
sp[0] = 0;
for(int i = 0; i < n; i++){
sp[i + 1] = sp[i] + y[i];
}
/*cout << "y : ";
for(int i = 0; i < n; i++) cout << y[i] << " ";
cout << '\n';
cout << "sp : ";
for(int i = 0; i <= n; i++) cout << sp[i] << " ";
cout << '\n';*/
i1 = 0, i2 = 0;
l = 0, r = dy;
ll mini1 = -1;
for(;r <= y.back(); l++, r++){
while(i2 < y.size() && y[i2] <= r) i2++;
while(i1 < y.size() && y[i1] < l) i1++;
//cout << "l = " << l << " r = " << r << " i1 = " << i1 << " i2 = " << i2;
ll sum = 0;
sum += l * i1 - sp[i1];
sum += (sp[n] - sp[i2]) - r * (n - i2);
//cout << " sum = " << sum << '\n';
//cout << " -- > l = " << l * i1 - sp[i1] << '\n';
//cout << " -- > r = " << (sp[n] - sp[i2]) - r * (n - i2) << '\n';
if(mini1 == -1 || sum < mini1) mini1 = sum;
}
//cout << "mini m pe oy = " << mini1 << '\n';
fout << mini + mini1 << '\n';
return 0;
}