ebubu @ 2021-06-11 14:14:13
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<math.h>
#include<algorithm>
using namespace std;
const int INF = 2 << 20;
struct point
{
double x;
double y;
};
point p[100000];
int temp[100000];
double dist(int i, int j)
{
double x = (p[i].x - p[j].x) * (p[i].x - p[j].x);
double y = (p[i].y - p[j].y) * (p[i].y - p[j].y);
return sqrt(x + y);
}
bool cmp(const point &a, const point &b)
{
if (a.x == b.x)
return a.y < b.y;
else
return a.x < b.x;
}
bool cmp2(const int& a, const int& b)
{
return p[a].y < p[b].y;
}
double min(double a, double b)
{
return a < b ? a : b;
}
double merge(int left, int right)
{
double d = INF;
if (left == right)
return d;
if (left + 1 == right)
return dist(left, right);
int mid = left+right>>1;
double l=merge(left, mid);
double r=merge(mid + 1, right);
d = min(1, r);
int i, j, k = 0;
for (i = left; i <= right; i++)
if (fabs(p[mid].x-p[i].x) <= d)
temp[k++] = i;
sort(temp, temp + k, cmp2);
for (i = 0; i < k; i++)
for (j = i + 1; j < k && (p[temp[j]].y - p[temp[i]].y) < d; j++)
{
double m = dist(temp[i], temp[j]);
if (d > m)
d = m;
}
return d;
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> p[i].x >> p[i].y;
sort(p, p + n, cmp);
printf("%.4lf\n", merge(0, n - 1));
}
我感觉没错啊 但是代码过不了 帮帮忙
by 阿丑 @ 2021-06-11 14:17:03
主页双帖,___