Cod sursa(job #2958771)

Utilizator ezluciPirtac Eduard ezluci Data 28 decembrie 2022 11:37:45
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#ifdef EZ
   #include "./ez/ez.h"
#else
   #include <bits/stdc++.h>
#endif
#define mp make_pair
#define mt make_tuple
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const string FILE_NAME = "cmap";
ifstream fin (FILE_NAME + ".in");
ofstream fout (FILE_NAME + ".out");

const int nMAX = 100e3;

int n;
pair<int, int> v[nMAX + 1];


auto cmpX = [](const pair<int, int> &a, const pair<int, int> &b) {
   return (a.fi < b.fi  ||  a.fi == b.fi && a.se < b.se);
};

auto cmpY = [](const pair<int, int> &a, const pair<int, int> &b) {
   return (a.se < b.se  ||  a.se == b.se && a.fi < b.fi);
};

long double dist(pair<int, int> a, pair<int, int> b)
{
   return sqrt((a.fi-b.fi)*1LL*(a.fi-b.fi) + (a.se-b.se)*1LL*(a.se-b.se));
}

long double distmin(int st, int dr)
{
   long double dmin = 9e15;

   if (dr-st+1 <= 3)
   {
      for (int i = st; i < dr; ++i)
         for (int j = i+1; j <= dr; ++j)
            dmin = min(dmin, dist(v[i], v[j]));
      return dmin;
   }

   int mj = st+dr >> 1;
   dmin = min(dmin, distmin(st, mj));
   dmin = min(dmin, distmin(mj+1, dr));

   vector<pair<int, int>> strip;
   for (int i = st; i <= dr; ++i)
      if (abs(v[i].fi - v[mj].fi) <= dmin)
         strip.pb(v[i]);
   
   sort(strip.begin(), strip.end(), cmpY);
   
   for (int i = 0; i < strip.size(); ++i)
      for (int j = i+1; j < strip.size() && strip[j].se - strip[i].se < dmin; ++j)
         dmin = min(dmin, dist(strip[i], strip[j]));

   return dmin;
}


int main()
{
   fin >> n;
   for (int i = 1; i <= n; ++i)
      fin >> v[i].fi >> v[i].se;
   
   sort(v + 1, v + n+1, cmpX);

   fout << setprecision(20) << distmin(1, n);
}