Pagini recente » Cod sursa (job #683617) | Cod sursa (job #1573062)
/**
* Worg
*/
#include <cstdio>
#include <algorithm>
using namespace std;
FILE *fin = freopen("tribute.in", "r", stdin);
FILE *fout = freopen("tribute.out", "w", stdout);
const int MAX_N = 50000;
const long long MAX_INF = 1000000000000000;
struct punct {
int x;
int y;
};
punct v[1 + MAX_N];
int n, dx, dy;
long long int sum[1 + MAX_N];
long long int sol1, sol2;
void readData() {
scanf("%d%d%d", &n, &dx, &dy);
for(int i = 1; i <= n; ++i)
scanf("%d%d", &v[i].x, &v[i].y);
}
bool dupaX(const punct &p1, const punct &p2) {
return p1.x < p2.x;
}
bool dupaY(const punct &p1, const punct &p2) {
return p1.y < p2.y;
}
void baleiereDupaX() {
sort(v + 1, v + n + 1, dupaX);
for(int i = 1; i <= n; ++i)
sum[i] = sum[i - 1] + v[i].x;
int st, dr;
int indSt = 1, indDr = 1;
sol1 = MAX_INF;
for(st = 0, dr = dx; dr <= MAX_N; st++, dr++) {
while(indSt <= n && v[indSt].x <= st) {
indSt++;
}
while(indDr <= n && v[indDr].x <= dr) {
indDr++;
}
//printf("%d %d ", indSt, indDr);
long long int a = 1LL * (indSt - 1) * st - sum[indSt - 1];
long long int b;
if(indDr > n) {
b = 0;
}
else {
b = sum[n] - sum[indDr - 1] - 1LL * (n - indDr + 1) * dr;
}
// printf("%lld %lld\n", a, b);
sol1 = min(sol1, a + b);
}
}
void baleiereDupaY() {
sort(v + 1, v + n + 1, dupaY);
for(int i = 1; i <= n; ++i)
sum[i] = sum[i - 1] + v[i].y;
int st, dr;
int indSt = 1, indDr = 1;
sol2 = MAX_INF;
for(st = 0, dr = dy; dr <= MAX_N; st++, dr++) {
while(indSt <= n && v[indSt].y <= st) {
indSt++;
}
while(indDr <= n && v[indDr].y <= dr) {
indDr++;
}
long long int a = 1LL * (indSt - 1) * st - sum[indSt - 1];
long long int b;
if(indDr > n) {
b = 0;
}
else {
b = sum[n] - sum[indDr - 1] - 1LL * (n - indDr + 1) * dr;
}
sol2 = min(sol2, a + b);
}
}
int main() {
readData();
baleiereDupaX();
baleiereDupaY();
printf("%lld", sol1 + sol2);
return 0;
}