Cod sursa(job #2089059)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 16 decembrie 2017 10:39:18
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.07 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];
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 brut(Punct p[], int n) {
  double result = FLT_MAX;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (dist(p[i], p[j]) < result)
        result = dist(p[i], p[j]);
    }
  }
  return result;
}

double minRamase(Punct ramase[], int n, double d) {
  double res = d;

  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n && (ramase[j].Y - ramase[i].Y) < res; j++) {
      double dd = dist(ramase[i], ramase[j]);
      res = min(res, dd);
    }
  }

  return res;
}

double divide(Punct px[], Punct py[], int n) {
  // STEP 1:
  if (n < 3)
    return brut(px, n);

  int mij = n / 2;
  Punct mp = px[mij];

  Punct *pLeft, *pRight;
  pLeft = new Punct[mij + 1];
  pRight = new Punct[n - mij - 1];
  int pl = 0, pr = 0;

  for (int i = 0; i < n; i++) {
    if(py[i].X <= mp.X)
      pLeft[pl++] = py[i];
    else pRight[pr++] = py[i];
  }

  // STEP 2

  double d = min(divide(px, pLeft, mij), divide(px + mij, pRight, n - mij));

  // STEP 3
  Punct* ramase;
  ramase = new Punct[n];
  int ramaseDim = 0;

  for (int i = 0; i < n; i++) {
    if (abs(py[i].X - mp.X) < d)
      ramase[ramaseDim++] = py[i];
  }

  // STEP 4 (done at beginning)

  // STEP 5 and 6
  return min(d, minRamase(ramase, ramaseDim, d));
}

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

  citire();
  cout << fixed << sqrt(divide(px, py, n));

  return 0;
}