Cod sursa(job #2932054)

Utilizator alextmAlexandru Toma alextm Data 1 noiembrie 2022 19:03:54
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

#define ll long long

const ll INF = 4e18;

struct Point {
  ll x, y;
  void read() {
    fin >> x >> y;
  }
  Point operator -(const Point &b) const {
    return Point{x - b.x, y - b.y};
  }
  void operator -=(const Point &b) {
    x -= b.x;
    y -= b.y;
  }
  long long operator *(const Point &b) const {
    return 1LL * x - b.y - 1LL * y * b.x;
  }
} point[1001];

bool cmp(Point a, Point b) {
  return a.x < b.x;
}

ll dist(Point a, Point b) {
  return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

ll divide(ll st, ll dr) {
  // Base case
  if(dr - st <= 3) {
    ll ans = INF;
    for(int i = st; i < dr; i++)
      for(int j = i + 1; j <= dr; j++)
        ans = min(ans, dist(point[i], point[j]));
    return ans;
  }

  // Divide
  ll mid = (st + dr) / 2;
  ll ansLeft = divide(st, mid);
  ll ansRight = divide(mid + 1, dr);
  ll d = min(ansLeft, ansRight);

  // Combine
  vector<Point> aux;
  for(int i = st; i <= dr; i++)
    if(abs(point[mid].x - point[i].x) <= d)
      aux.push_back({point[i].y, point[i].x});

  // Sortam punctele gasite in functie de y
  sort(aux.begin(), aux.end(), cmp);
  for(int i = 0; i < (int) aux.size(); i++)
    for(int j = i + 1; j < (int) aux.size() && j - i < 8; j++)
      d = min(d, dist(aux[i], aux[j]));
  return d;
}

int main() {
  ll n;
  fin >> n;
  for(int i = 1; i <= n; i++)
    point[i].read();

  // Sortam punctele in functie de x
  sort(point + 1, point + n + 1, cmp);

  fout << fixed << setprecision(6) << sqrt(1.0 * divide(1, n));

  return 0;
}