Pagini recente » Cod sursa (job #1104422) | Cod sursa (job #1948506) | Cod sursa (job #889692) | Cod sursa (job #529207) | Cod sursa (job #447103)
Cod sursa(job #447103)
#include <iostream>
using namespace std;
#define maxn 50010
#define inf 99999999
int N, DX, DY;
long long sol, solx, soly;
int x[maxn], y[maxn];
int main() {
FILE *f1=fopen("tribute.in", "r"), *f2=fopen("tribute.out", "w");
int i, j, p, q, k;
int pos, start, end;
long long sum;
fscanf(f1, "%d %d %d\n", &N, &DX, &DY);
for(i=1; i<=N; i++) {
fscanf(f1, "%d %d\n", &x[i], &y[i]);
}
solx = soly = inf;
sort(x+1, x+N+1);
sort(y+1, y+N+1);
//aflu suma minima pe x
pos = 0; sum = 0;
start = 0; end = DX;
for(i=1; i<=N; i++) {
if(x[i] > end) {
sum += (x[i] - end);
}
}
solx = min(solx, sum);
while(pos <= x[N]) {
//plasez acum in punctul pos + 1
pos++;
start = pos; end = pos + DX;
//caut binar numarul de pcte din dreapta - afara
p = upper_bound(x+1, x+N+1, end - 1) - x;
q = lower_bound(x+1, x+N+1, start) - x - 1;
sum += q; sum -= (N - p + 1);
solx = min(solx, sum);
}
//aflu suma minima pe y
pos = 0; sum = 0;
start = 0; end = DY;
for(i=1; i<=N; i++) {
if(y[i] > end) {
sum += (y[i] - end);
}
}
soly = min(soly, sum);
while(pos <= y[N]) {
//plasez acum in punctul pos + 1
pos++;
start = pos; end = pos + DY;
//caut binar numarul de pcte din dreapta - afara
p = upper_bound(y+1, y+N+1, end - 1) - y;
q = lower_bound(y+1, y+N+1, start) - y - 1;
sum += q; sum -= (N - p + 1);
soly = min(soly, sum);
}
sol = solx + soly;
if(N==0) fprintf(f2, "%d\n", 0);
else fprintf(f2, "%lld\n", solx + soly);
fclose(f1); fclose(f2);
return 0;
}