Cod sursa(job #2096768)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 29 decembrie 2017 18:50:40
Problema Tribute Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <cstdio>

const int MAXN = 5e4 + 1;
const int INF = 2e9;

int xst[MAXN + 1], xdr[MAXN + 1], yst[MAXN + 1], ydr[MAXN + 1];

int main() {
  int n, dx, dy, x, y, minx, miny;
  FILE *f = fopen("tribute.in", "r");
  fscanf(f, "%d%d%d", &n, &dx, &dy);
  for (int i = 0; i < n; ++i) {
    fscanf(f, "%d%d",  &x, &y);
    ++xst[x + 1];
    ++xdr[y + 1];
    ++yst[x + 1];
    ++ydr[y + 1];
  }
  fclose(f);
  for (int i = 1; i <= MAXN; ++i) {
    xst[i] += xst[i - 1];
    yst[i] += yst[i - 1];
  }
  for (int i = 1; i <= MAXN; ++i) {
    xst[i] += xst[i - 1];
    yst[i] += yst[i - 1];
  }
  for (int i = MAXN; i > 0; --i) {
    xdr[i] += xdr[i + 1];
    ydr[i] += ydr[i + 1];
  }
  for (int i = MAXN; i > 0; --i) {
    xdr[i] += xdr[i + 1];
    ydr[i] += ydr[i + 1];
  }
  minx = INF;
  for (int i = 1; i <= MAXN - dx; ++i) {
    if (xst[i - 1] + xdr[i + dx + 1] < minx) {
      minx = xst[i - 1] + xdr[i + dx + 1];
    }
  }
  miny = INF;
  for (int i = 1; i <= MAXN - dy; ++i) {
    if (yst[i - 1] + ydr[i + dy + 1] < miny) {
      miny = yst[i - 1] + ydr[i + dy + 1];
    }
  }
  f = fopen("tribute.out", "w");
  fprintf(f, "%d\n", minx + miny);
  fclose(f);
  return 0;
}