Cod sursa(job #2135159)

Utilizator xRoALexBirtoiu Alexandru xRoALex Data 18 februarie 2018 17:20:54
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <cstdio>
#include <vector>
#include <cstdio>
#include <algorithm>

#define x first
#define y second
#define INF 1e18
using namespace std;

FILE *in = fopen("cmap.in", "r");
FILE *out = fopen("cmap.out", "w");

const int maxN = 1e5 + 5;
const long long inf = 1e18;
const int maxDiff = 8;

int n;
 pair<int, int > pts[maxN], aux[maxN];

void citire() {
  fscanf(in,"%d", &n);
  for(int i = 0; i < n; i++) {
    fscanf(in,"%d%d", &pts[i].x, &pts[i].y);
  }
}

void Merge(int left, int mid, int right) {
  int p1 = left, p2 = mid + 1, pos = 0;

  while(p1 <= mid && p2 <= right)
  {
    if(pts[p1].y < pts[p2].y)
    {
      aux[pos] = pts[p1]; p1++; pos++;
    } else
    {
      aux[pos] = pts[p2]; p2++; pos++;
    }
  }

  while(p1 <= mid)
    {
    aux[pos] = pts[p1]; p1++; pos++;
    }

  while(p2 <= right)
  {
    aux[pos] = pts[p2]; p2++; pos++;
  }

  for(int i = 0; i < pos; i++) {
    pts[left + i] = aux[i];
  }
}

long long dist( pair<int, int > A,  pair<int, int > B) {
  return 1LL * (A.x - B.x) * (A.x - B.x) + 1LL * (A.y - B.y) * (A.y - B.y);
}

long long divide(int left, int right) {
  if(right - left < 2)
    {
    if(right == left)
      return inf;
  else {
      Merge(left, left, right);
      return dist(pts[left], pts[right]);
    }
  }

  int mid = (left + right) / 2;
  long long d1 = divide(left, mid), d2 = divide(mid + 1, right);

  long long d = min(d1, d2);
  Merge(left, mid, right);

  for(int i = left; i <= right; i++)
    for(int j = i - 1; j >= left && i - j < maxDiff; j--)
      d = min(d, dist(pts[i], pts[j]));

  return d;
}

int main() {
  citire();

  sort(pts, pts + n);

  fprintf(out,"%.7f\n", sqrt((double)divide(0, n - 1)));

  return 0;
}