Cod sursa(job #447103)

Utilizator vladiiIonescu Vlad vladii Data 27 aprilie 2010 18:33:36
Problema Tribute Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#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;
}