C++分治

题意：二维最近点对

#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;
}