Cod sursa(job #2089134)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 16 decembrie 2017 11:04:45
Problema Cele mai apropiate puncte din plan Scor 65
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>
using namespace std;

#define Punct pair<double, double>
#define X first
#define Y second
#define NMAX 100005

double sqr(double x) { return x * x; }

Punct px[NMAX];
Punct py[NMAX];
Punct aux[NMAX];
int n;

bool dupaX(Punct a, Punct b) {
  if (a.X == b.X)
    return a.Y < b.Y;
  return a.X < b.X;
}

bool dupaY(Punct a, Punct b) {
  if (a.Y == b.Y)
    return a.X < b.X;
  return a.Y < b.Y;
}

void citire() {
  scanf("%d ", &n);

  for (int i = 0; i < n; i++) {
    double x, y;
    scanf("%lf %lf ", &x, &y);
    px[i] = { x, y };
    py[i] = { x, y };
  }

  sort(px, px + n, dupaX);
  sort(py, py + n, dupaY);
}

double dist(Punct a, Punct b) {
  return sqr(a.X - b.X) + sqr(a.Y - b.Y);
}

double divide(int st, int dr) {
  if (st == dr)
    return DBL_MAX;

  if (abs(st - dr) == 1)
    return dist(py[st], py[dr]);

  int mij = (st + dr) / 2;

  double res = min(divide(st, mij), divide(mij + 1, dr));

  merge(py + st, py + mij + 1, py + mij + 1, py + dr + 1, aux);
  copy(aux, aux + (dr - st + 1), py + st);

  int k = 0;

  for (int i = st; i <= dr; i++) {
    if (abs(px[mij].X - py[i].Y) <= res && i != mij)
      aux[k++] = py[i];
  }

  for (int i = 0; i < k; i++)
    for (int j = i + 1; j < k && j <= i + 8; j++)
      res = min(res, dist(aux[i], aux[j]));

  return res;
}

int main() {
  freopen("cmap.in", "r", stdin);
  freopen("cmap.out", "w", stdout);

  citire();
  cout << fixed << sqrt(divide(0, n - 1));

  return 0;
}