题意：二维最近点对
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include <cstring>
using namespace std;
const int N = 100005;
const double INF = 1e20;
struct node{
double x;
double y;
}str[N];
double min(double a, double b)
{
return a < b ? a : b;
}
bool cmp(node a, node b)
{
if (a.x!=b.x)
return a.x<b.x;
return a.y < b.y;
}
int te[N];
int n;
double dis(int a, int b)
{
return sqrt((str[a].x - str[b].x)*(str[a].x - str[b].x) + (str[a].y - str[b].y)*(str[a].y - str[b].y));
}
bool cmpp(int a, int b)
{
return str[a].y < str[b].y;
}
double fun(int left, int right)
{
double d = INF;
if (left == right)
{
return d;
}
if (left + 1 == right)
{
return dis(left, right);
}
int mid;
mid = (left + right) >> 1;
double d1 = fun(left, mid);
double d2 = fun(mid + 1, right);
d = min(d1, d2);
double d3;
int i, j, k = 0;
for (i = left; i <= right; i++)
{
if (fabs(str[i].x - str[mid].x) < d)
{
te[k++] = i;
}
}
sort(te, te + k, cmpp);
for (i = 0; i < k; i++)
{
for (j = i + 1; j < k&&fabs(str[te[i]].y - str[te[j]].y)<d; j++)
{
d3 = dis(te[i], te[j]);
if (d>d3)
{
d = d3;
}
}
}
return d;
}
int main()
{
scanf("%d", &n);
int i;
for (i = 0; i < n;i++)
scanf("%lf %lf", &str[i].x, &str[i].y);
sort(str, str + n, cmp);
printf("%.2lf\n", fun(0, n - 1));
return 0;
}
