Cod sursa(job #2818484)

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

using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
vector<point> xs, ys, zs;
int n;

void read()
{
  f>>n;
  long long x, y;
  for(int i = 1;i <= n;++i)
    f>>x>>y, xs.push_back(make_pair(x, y));
  
  sort(xs.begin(), xs.end());

  for(point punct : xs)
    ys.push_back(make_pair(punct.y, punct.x));
}

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

long long compute(long long left, long long right)
{
  if(left >= right)
    return oo;
  
  if(right - left == 1)
    return distance(xs[left], xs[right]);
  
  long long mid = (left + right) >> 1;
  long long best = min(compute(left, mid), compute(mid, right));

  sort(ys.begin() + left, ys.begin() + right);
  zs.clear();

  for(int i = left;i < right;++i)
    if(abs(ys[i].y - xs[mid].x) <= best)  
      zs.push_back(ys[i]);
  
  for(int i = 0;i < zs.size() - 1;++i)
    for(int j = i + 1;j < zs.size() && j - i < 8;++j)
      best = min(best, distance(zs[i], zs[j]));
  
  return best;
}

void solve()
{
  g<<setprecision(6)<<fixed<<sqrt(compute(0, n));
}

int main()
{
  read();
  solve();
  return 0;
}