Cod sursa(job #2721405)

Utilizator victorzarzuZarzu Victor victorzarzu Data 11 martie 2021 19:29:56
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
#define oo 0x3f3f3f3f 
#define point pair<long long, long long>
#define x first
#define y second

using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
int n;
vector<point> x, y, v;

long long dist(point p1, point p2)
{
  return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}


long long solve(int st, int dr)
{
  if(st >= dr)
    return oo;
  if(dr - st == 1)
    return dist(x[st], x[st + 1]);
  int mid = (st + dr) >> 1;
  long long best = min(solve(st, mid), solve(mid, dr));

  sort(y.begin() + st, y.begin() + dr); //sortare in functie de ordonata

  v.clear();
  for(int i = st;i < dr;++i)
    if(abs(y[i].y - x[i].x) <= best)
      v.push_back(y[i]);
  for(int i = 0;i < v.size();++i)
    for(int j = i + 1;j < v.size() && j - i < 8;++j)
      best = min(best, dist(v[i], v[j]));
  return best;
}

void Read()
{
  long long a, b;
  f>>n;
  for(int i = 1;i <= n;++i)
    f>>a>>b, x.push_back(make_pair(a, b));

  sort(x.begin(), x.end());
  for(auto it : x)
    y.push_back(make_pair(it.y, it.x));
  
  g<<setprecision(6)<<fixed<<sqrt(solve(0, n));
}


int main()
{
  Read();
  return 0;
}