Cod sursa(job #3363433)

Utilizator Cezar2009Cezar Mihai Titihazan Cezar2009 Data 17 august 2026 23:41:21
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.91 kb
// https://www.infoarena.ro/problema/cmap

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#elif __GNUC__
#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif

// #define _USE_MATH_DEFINES

#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <fstream>
#include <iostream>
#include <utility>
#include <vector>
// #include <array>
// #include <list>
// #include <forward_list>
// #include <string>
// #include <cstring>
// #include <cmath>
// #include <bitset>
// #include <queue>
// #include <stack>
// #include <map>
// #include <set>
// #include <unordered_map>
// #include <unordered_set>
#include <limits>
// #include <climits>
#include <iomanip>
// #include <tuple>
// #include <numeric>
// #include <chrono>
#include <memory>

using namespace std;

using int64 = int64_t;
using uint64 = uint64_t;
using int16 = int16_t;
using uint16 = uint16_t;
using pii = pair<int, int>;
using pll = pair<int64, int64>;

#define all(x) (x).begin(), (x).end()
#define allg(x) (x).begin(), (x).end(), greater<int>()
#define sz(x) (int)(x).size()
#define pb push_back
#define eb emplace_back
#define rfor(i, st, dr) for (auto i = (st); i <= (dr); ++i)
#define for0(i, n) for (auto i = 0; i < (n); ++i)
#define rfor0(i, n) for (auto i = (n) - 1; i >= 0; --i)
#define for1(i, n) for (auto i = 1; i <= (n); ++i)
#define rfor1(i, n) for (auto i = (n); i >= 1; --i)
#define foreach(x, a) for (auto &x : a)
#define cforeach(x, a) for (const auto &x : a)
#define ft first
#define sd second
#define cendl cout << "\n"
#define fendl fout << "\n"
#define FASTIO                                                                 \
  ios::sync_with_stdio(false);                                                 \
  cin.tie(nullptr);

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

// FILE* fin = fopen("cmap.in", "r");
// FILE* fout = fopen("cmap.out", "w");

template <typename T> class FastIO {
private:
  ifstream &fin;
  ofstream &fout;

  static constexpr int IN_BUF_SIZE = 262144;
  static constexpr int OUT_BUF_SIZE = 262144;

  char inBuf[IN_BUF_SIZE];
  int inPos = IN_BUF_SIZE, inBytes = IN_BUF_SIZE;

  char outBuf[OUT_BUF_SIZE];
  int outPos = 0;

  inline char getChar() {
    if (inPos == inBytes) {
      fin.read(inBuf, IN_BUF_SIZE);
      inBytes = fin.gcount();
      inPos = 0;
      if (inBytes == 0)
        return -1;
    }

    return inBuf[inPos++];
  }

  inline void writeChar(char c) {
    if (outPos == OUT_BUF_SIZE) {
      fout.write(outBuf, outPos);
      outPos = 0;
    }
    outBuf[outPos++] = c;
  }

  T read() {
    char c;
    bool neg = false;

    do {
      c = getChar();
      if (c == -1)
        return -1;
    } while ((c < '0' || c > '9') && c != '-');

    if (c == '-') {
      neg = true;
      c = getChar();
    }

    T res = 0;
    while (c >= '0' && c <= '9') {
      res = res * 10 + (c - '0');
      c = getChar();
    }
    return neg ? -res : res;
  }

  void write(T x) {
    if (x < 0) {
      writeChar('-');
      x = -x;
    }

    char temp[20];
    int len = 0;
    do {
      temp[len++] = '0' + x % 10;
      x /= 10;
    } while (x);

    while (len--)
      writeChar(temp[len]);
  }

public:
  FastIO(ifstream &finStream, ofstream &foutStream)
      : fin(finStream), fout(foutStream) {}

  void flush() {
    if (outPos > 0) {
      fout.write(outBuf, outPos);
      outPos = 0;
    }
  }

  friend FastIO<T> &operator>>(FastIO<T> &io, T &x) {
    x = io.read();
    return io;
  }

  friend FastIO<T> &operator<<(FastIO<T> &io, T x) {
    io.write(x);
    return io;
  }

  friend FastIO &operator<<(FastIO &io, const char *s) {
    for (int i = 0; s[i]; ++i)
      io.writeChar(s[i]);
    return io;
  }
};

const int NRMAX = 100000;

struct Punct {
  int x, y;

  bool operator<(const Punct &other) const {
    if (this->x == other.x)
      return this->y < other.y;
    return this->x < other.x;
  }
};

Punct p[NRMAX + 1];
Punct m[NRMAX + 1];
int n;

double Q_rsqrt(int64 number) {
  long long i;
  double x2, y;

  x2 = number * 0.5;
  y = number;

  i = *(long long *)&y;

  i = 0x5fe6eb50c7b537a9LL - (i >> 1);

  y = *(double *)&i;

  y = y * (1.5 - (x2 * y * y));
  y = y * (1.5 - (x2 * y * y));
  y = y * (1.5 - (x2 * y * y));
  y = y * (1.5 - (x2 * y * y));

  return y;
}
double Q_sqrt(int64 x) { return x * Q_rsqrt(x); }

int64 dist(const Punct &a, const Punct &b) {
  return (int64)(a.x - b.x) * (a.x - b.x) + (int64)(a.y - b.y) * (a.y - b.y);
}

int64 rezolvare(int st, int dr) {
  if (dr - st <= 3) {
    int64 mini = numeric_limits<int64>::max();
    for (int i = st; i <= dr; ++i)
      for (int j = i + 1; j <= dr; ++j)
        mini = min(mini, dist(p[i], p[j]));

    sort(p + st, p + dr + 1,
         [](const Punct &a, const Punct &b) { return a.y < b.y; });

    return mini;
  }

  int mij = (st + dr) / 2;
  int mijx = p[mij].x;

  int64 d1 = rezolvare(st, mij);
  int64 d2 = rezolvare(mij + 1, dr);
  int64 d = min(d1, d2);

  merge(p + st, p + mij + 1, p + mij + 1, p + dr + 1, m + st,
        [](const Punct &a, const Punct &b) { return a.y < b.y; });
  for (int i = st; i <= dr; i++)
    p[i] = m[i];

  vector<Punct> v;
  rfor(i, st, dr) if ((int64)(p[i].x - mijx) * (p[i].x - mijx) <= d) v.pb(p[i]);

  for0(i, sz(v)) for (int j = i + 1;
                      j < sz(v) && (v[j].y - v[i].y) * (v[j].y - v[i].y) < d;
                      ++j) d = min(d, dist(v[i], v[j]));

  return d;
}

int main() {
  FASTIO;

  FastIO<int> io(fin, fout);

  io >> n;

  for1(i, n) io >> p[i].x >> p[i].y;

  sort(p + 1, p + n + 1);

  /*for1(i, n)
          cout << p[i].x << " " << p[i].y << "\n";*/

  fout << setprecision(6) << fixed << Q_sqrt(rezolvare(1, n)) << "\n";
  fout.flush();

  fin.close();
  fout.close();

  return 0;
}