Cod sursa(job #556714)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 16 martie 2011 11:53:18
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 50005, INF = 2000000000;

int n, tot, dx, dy, x[N], y[N];

void read() {
  freopen("tribute.in", "r", stdin);
  freopen("tribute.out", "w", stdout);
  scanf("%d %d %d", &n, &dx, &dy);
  for (int i = 1; i <= n; ++ i)
    scanf("%d %d", &x[i], &y[i]);
}

void init() {
  sort(x + 1, x + n + 1);
  sort(y + 1, y + n + 1);
}

void solvex() {
  int xf = 0,xc = x[1] - 1, down = 0, in = 0, up = n, c = 0, rez = INF;

  for (int i = 1; i <= n; ++ i)
    c += x[i] - xc;
  c += n;

  while (xc <= x[n]) {
    c += down - up;

    if (c < rez) {
      rez = c;
      xf = xc;
    }

    while (x[down + in + 1] == xc + 1) {
      ++ in;
      -- up;
      -- c;
    }

    while (x[down + 1] == xc - dx) {
      ++ down;
      -- in;
    }

    ++ xc;
  }

  tot += rez;
}

void solvey() {
  int yf = 0, yc = y[1] - 1, left = 0, in = 0, right = n, c = 0, rez = INF;

  for (int i = 1; i <= n; ++ i)
    c += y[i] - yc;
  c += n;

  while (yc <= y[n]) {
    c += left - right;

    if ( c < rez) {
      rez = c;
      yf = yc;
    }

    while (y[left + in + 1] == yc + 1) {
      ++ in;
      -- right;
      -- c;
    }

    while (y[left + 1] == yc - dy) {
      ++ left;
      -- in;
    }

    ++ yc;
  }

  tot += rez;
}

int main() {
  read();
  init();
  solvex();
  solvey();
  printf("%d\n", tot);
  return 0;
}