Mai intai trebuie sa te autentifici.
Cod sursa(job #2958778)
Utilizator | Data | 28 decembrie 2022 12:01:02 | |
---|---|---|---|
Problema | Cele mai apropiate puncte din plan | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.85 kb |
#ifdef EZ
#include "./ez/ez.h"
#else
#include <bits/stdc++.h>
#endif
#define mp make_pair
#define mt make_tuple
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const string FILE_NAME = "cmap";
ifstream fin (FILE_NAME + ".in");
ofstream fout (FILE_NAME + ".out");
const int nMAX = 100e3;
int n;
pair<int, int> v[nMAX + 1];
auto cmpX = [](const pair<int, int> &a, const pair<int, int> &b) {
return (a.fi < b.fi || a.fi == b.fi && a.se < b.se);
};
auto cmpY = [](const pair<int, int> &a, const pair<int, int> &b) {
return (a.se < b.se || a.se == b.se && a.fi < b.fi);
};
long double dist(pair<int, int> a, pair<int, int> b)
{
return sqrt((a.fi-b.fi)*1LL*(a.fi-b.fi) + (a.se-b.se)*1LL*(a.se-b.se));
}
long double distmin(int st, int dr)
{
long double dmin = 9e15;
if (dr-st+1 <= 3)
{
for (int i = st; i < dr; ++i)
for (int j = i+1; j <= dr; ++j)
dmin = min(dmin, dist(v[i], v[j]));
sort(v + st, v + dr+1, cmpY);
return dmin;
}
int mj = st+dr >> 1;
int midx = v[mj].fi;
dmin = min(dmin, distmin(st, mj));
dmin = min(dmin, distmin(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(), cmpY);
copy(tmp.begin(), tmp.end(), v + st);
vector<pair<int, int>> strip;
for (int i = st; i <= dr; ++i)
if (abs(v[i].fi - midx) <= dmin)
strip.pb(v[i]);
sort(strip.begin(), strip.end(), cmpY);
for (int i = 0; i < strip.size(); ++i)
for (int j = i+1; j < strip.size() && strip[j].se - strip[i].se < dmin; ++j)
dmin = min(dmin, dist(strip[i], strip[j]));
return dmin;
}
int main()
{
fin >> n;
for (int i = 1; i <= n; ++i)
fin >> v[i].fi >> v[i].se;
sort(v + 1, v + n+1, cmpX);
fout << setprecision(20) << distmin(1, n);
}