Cod sursa(job #2969637)

Utilizator ezluciPirtac Eduard ezluci Data 23 ianuarie 2023 14:58:33
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 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)
{
   if (dr-st+1 <= 3)
   {
      sort(v + st, v + dr+1, [](const pair<int, int> &A, const pair<int, int> &B) {
         return A.se > B.se;
      });
      long double d = 9e15;
      for (int i = st; i <= dr; ++i)
         for (int j = i+1; j <= dr; ++j)
            d = min(d, dist(v[i], v[j]));
      
      return d;
   }

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

   int mj = st+dr >> 1;
   int mjx = v[mj].fi;
   long double d = min(solve(st, mj), solve(mj+1, dr));

   vector<pair<int, int>> tmp(dr-st+1);
   merge(v + st, v + mj+1, v + mj+1, v + dr+1, tmp.begin(), [](const pair<int, int> &A, const pair<int, int> &B) {
      return A.se > B.se;
   });
   copy(tmp.begin(), tmp.end(), v + st);

   vector<pair<int, int>> strip;
   for (int i = st; i <= dr; ++i)
      if (abs(mjx - v[i].fi) < d)
         strip.pb(v[i]);

   for (int i = 0; i < strip.size(); ++i)
      for (int j = i+1; j < strip.size() && strip[i].se - strip[j].se < d; ++j)
         d = min(d, dist(strip[i], strip[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;
   });

   cout << setprecision(15) << solve(1, n);
}