Cod sursa(job #2089126)

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

ifstream fin("cmap.in");
ofstream fout("cmap.out");

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

LL sqr(LL 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() {
  fin >> n;

  for (int i = 0; i < n; i++) {
    LL x, y;
    fin >> x >> y;
    px[i] = { x, y };
    py[i] = { x, y };
  }

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

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

LL divide(int st, int dr) {
  if (st == dr)
    return 1LL<<60;

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

  int mij = (st + dr) / 2;

  LL 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 + 6; j++)
      res = min(res, dist(aux[i], aux[j]));

  return res;
}

int main() {
  citire();
  fout << fixed << sqrt(divide(0, n - 1));

  return 0;
}