低焓体 @ 2019-02-10 21:58:24
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
const double INF = 1e20;
struct Point {
double x, y;
bool operator<(Point &pt) {
if (x == pt.x) return y < pt.y;
else return x < pt.x;
}
bool operator>(Point &pt) {
return !(*this < pt);
}
};
Point pset[200005];
int near[200005], nearn;
int psetn, hn;
inline void swap(Point &p1, Point &p2)
{
Point pt;
pt = p1;
p1 = p2;
p2 = pt;
}
void push(Point x)
{
pset[++hn] = x;
int p = hn, f;
while (p >= 2) {
f = p >> 1;
if (pset[f] > pset[p]) break;
swap(pset[f], pset[p]);
p = f;
}
}
void pop()
{
swap(pset[1], pset[hn--]);
int p = hn, k, mhn = hn << 1;
while (p <= mhn) {
k = p << 1;
if (k + 1 <= hn && pset[k + 1] > pset[k]) k++;
if (pset[p] > pset[k]) break;
swap(pset[p], pset[k]);
p = k;
}
}
void hsort()
{
for (int i = 1; i <= psetn; i++) push(pset[i]);
for (int i = 1; i <= psetn; i++) pop();
}
inline double min(double d1, double d2)
{
return d1 < d2 ? d1 : d2;
}
inline double sqr(double x)
{
return x * x;
}
inline double dis2(Point &p1, Point &p2)
{
return sqr(p1.x - p2.x) + sqr(p1.y - p2.y);
}
double dc(int l, int r)
{
double mdis = INF;
if (l == r) return mdis;
int mid = (l + r) >> 1;
mdis = min(dc(l, mid), dc(mid + 1, r));
for (int i = l; i <= r; i++)
if (sqr(pset[i].x - pset[mid].x) < mdis) near[++nearn] = i;
for (int i = 1; i < nearn; i++)
for (int j = i + 1; j <= nearn && sqr(pset[i].y - pset[j].y) < mdis; j++)
mdis = min(mdis, dis2(pset[near[i]], pset[near[j]]));
nearn = 0;
return mdis;
}
int main()
{
ios::sync_with_stdio(false);
cin >> psetn;
for (int i = 1; i <= psetn; i++)
cin >> pset[i].x >> pset[i].y;
hsort();
cout << fixed << setprecision(4) << sqrt(dc(1, psetn));
return 0;
}
by 白菜道士 @ 2019-07-11 14:55:59
看不懂你写的 看这个
by 白菜道士 @ 2019-07-11 15:05:36
@dihanti 真的看不懂你写的,我理解能力太差,qwq.