洛谷 P1429 平面最近点对(加强版)

https://www.luogu.com.cn/problem/P1429

 

分治法

将点对从中间分成两个集合Sl,Sr,分别递归求Sl内的最近点对,Sr内的最近点对

合并时,若Sl内部最近点对距离d1,Sr为d2

令d=min(d1,d2)

暴力算分界线往左往右d距离内的点对距离即可

这些点不会很多

 

#include<cmath>
#include<cstdio>
#include<algorithm>

using namespace std;

#define N 200001

const double inf=1e11;

struct node
{
    double x,y;
}e[N];

int a[N];

bool cmp(node p,node q)
{
    return p.x<q.x;
}

double getdis(int p,int q)
{
    return sqrt((e[p].x-e[q].x)*(e[p].x-e[q].x)+(e[p].y-e[q].y)*(e[p].y-e[q].y)); 
}

double solve(int l,int r)
{
    if(l==r) return inf;
    int mid=l+r>>1;
    double d1=solve(l,mid);
    double d2=solve(mid+1,r);
    double d=min(d1,d2);
    int m=0;
    for(int i=l;i<=r;++i)
        if(abs(e[i].x-e[mid].x)<=d) a[++m]=i;
    for(int i=1;i<m;++i)
        for(int j=i+1;j<=m;++j)
            d=min(d,getdis(a[i],a[j]));
    return d;
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%lf%lf",&e[i].x,&e[i].y);
    sort(e+1,e+n+1,cmp);
    printf("%.4lf",solve(1,n)); 
}     

 

题目描述

给定平面上n个点,找出其中的一对点的距离,使得在这n个点的所有点对中,该距离为所有点对中最小的

输入格式

第一行:n;2≤n≤200000

接下来n行:每行两个实数:x y,表示一个点的行坐标和列坐标,中间用一个空格隔开。

输出格式

仅一行,一个实数,表示最短距离,精确到小数点后面4位。

输入输出样例

输入 #1
3
1 1
1 2
2 2
输出 #1
1.0000

说明/提示

0<=x,y<=10^9

上一篇:从心开始的CentOS学习笔记之七:文件目录操作cp rm mv basename dirname


下一篇:初始化出库任务