Cod sursa(job #1689148)

Utilizator lflorin29Florin Laiu lflorin29 Data 13 aprilie 2016 23:24:31
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;

struct Point
{
  int x, y;
  Point(int x = 0, int y = 0) : x(x), y(y) {};

  double dist(const Point &other) const
  {
    double d1 = x - other.x, d2 = y - other.y;
    return (d1 * d1 + d2 * d2);
  }
};

const double INF = 1e15;

vector<Point>V;
int N;

void Read()
{
  ifstream in("cmap.in");
  in >> N; V.resize(N);
  for(auto &act : V)
    in >> act.x >> act.y;
  sort(begin(V), end(V), [&] (const Point &a, const Point &b) { return a.x < b.x;});
}

double foo(int x , int y)
{
  if(x == y) return 0;
  if(y - x + 1 <= 3)
  {
    double ans = INF;
    for(int i = x; i <= y; ++i)
      for(int j = i + 1; j <= y; ++j) ans = min(ans, V[i].dist(V[j]));
    return ans;
  }

  int mij = (x + y) / 2;
  double better = min(foo(x, mij), foo(mij+1, y));
  vector <Point>strip;
  for(int k = x; k<= y; ++k)
     if(fabs(V[k].x - V[mij].x) <= better)
    strip.push_back(V[k]);
  auto cmp = [&] (const Point &a, const Point &b) { return a.y < b.y;};
  sort(begin(strip), end(strip), cmp);
  for(int i = 0; i < (int)strip.size(); ++i)
    for(int j = i + 1; j < (int)strip.size() && strip[i].dist(strip[j]) < better; ++j)
       better = min(better, strip[i].dist(strip[j]));
  return better;
}

int main()
{
  Read();
  ofstream("cmap.out")<<fixed<<setprecision(9)<<sqrt(foo(0, V.size() - 1));
  return 0;
}