Cod sursa(job #2969510)

Utilizator ezluciPirtac Eduard ezluci Data 23 ianuarie 2023 12:03:49
Problema Cele mai apropiate puncte din plan Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 kb
using namespace std;
#ifdef EZ
   #include "./ez/ez.h"
   const string FILE_NAME = "test";
#else
   #include <bits/stdc++.h>
   const string FILE_NAME = "cmap";
#endif
#define mp make_pair
#define mt make_tuple
#define ll long long
#define pb push_back
#define fi first
#define se second
#define cin fin
#define cout fout
ifstream fin (FILE_NAME + ".in");
ofstream fout (FILE_NAME + ".out");

const int nMAX = 100e3;

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


long double dist(pair<int, int> A, pair<int, int> B)
{
   return sqrt((long double) (A.fi-B.fi) * (A.fi-B.fi) + (long double) (A.se-B.se) * (A.se-B.se));
}


long double solve(int st, int dr, vector<pair<int, int>> &s)
{
   if (dr-st+1 <= 3)
   {
      s.resize(dr-st+1);
      copy(v + st, v + dr+1, s.begin());
      sort(s.begin(), s.end(), [](const pair<int, int> &A, const pair<int, int> &B) {
         return A.se > B.se;
      });
      long double d = 9e15;
      for (int i = 0; i < s.size(); ++i)
         for (int j = i+1; j < s.size(); ++j)
            d = min(d, dist(s[i], s[j]));
      
      return d;
   }

   vector<pair<int, int>> s1, s2;

   int mj = st+dr >> 1;
   long double d = 9e15;
   d = min(d, solve(st, mj, s1));
   d = min(d, solve(mj+1, dr, s2));

   vector<pair<int, int>> S1, S2;
   for (auto x : s1)
      if (v[mj].fi - x.fi <= d)
         S1.pb(x);
   for (auto x : s2)
      if (x.fi - v[mj].fi <= d)
         S2.pb(x);


   s.resize(S1.size() + S2.size());
   merge(S1.begin(), S1.end(), S2.begin(), S2.end(), s.begin(), [](const pair<int, int> &A, const pair<int, int> &B) {
      return A.se > B.se;
   });

   for (int i = 0; i < s.size(); ++i)
      for (int j = i+1; j < s.size() && s[i].se - s[j].se < d; ++j)
         d = min(d, dist(s[i], s[j]));
   
   return d;
}


int main()
{
   cin >> n;
   for (int i = 1; i <= n; ++i)
      cin >> v[i].fi >> v[i].se;
   
   sort(v + 1, v + n+1, [](const pair<int, int> &A, const pair<int, int> &B) {
      return A.fi < B.fi;
   });

   vector<pair<int, int>> s;
   cout << setprecision(15) << solve(1, n, s);
}