洛谷 P1257 平面上的最接近点对 题解

P1257 平面上的最接近点对

题目描述

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

输入格式

第一行：n；2≤n≤10000

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

输出格式

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

输入输出样例

输入 #1

3
1 1
1 2
2 2

输出 #1

1.0000

说明/提示

本题爆搜即可

【思路】

分治 + 枚举
话说我也不知道为什么标签上面会有分治
可能用分治会跑的更快吧
但是这道题目完全是可以用枚举过掉的
本来还是有点难度的
但是一旦可以用枚举过掉
那就是一道大水题了

不过还是有两个值得注意的地方的

min和max只能比较两个相同定义类型的变量
是没有办法比较两个不用定义类型的变量的
比如他可以比较两个double类型的大小，也可以比较两个int类型的大小
但是一旦比较一个double和一个int类型的大小就会编译错误
所以这里的最小值Min需要定义成double类型的
因为两点之间距离公式如果用cmath库里面的sqrt求的话
那返回值是double类型的
float也不行哦！
并且输出的时候有精度，
当然是double更好地啦

另一个值得注意的问题就是两点之间求根公式啦
两点之间的距离等于\(\sqrt {(x_1 - x_2)^2 + (y_1 - y_2)^2}\)

【完整代码】

#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;
const int Max = 10005;
struct node
{
    int x,y;
}a[Max];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1;i <= n;++ i)
        scanf("%d%d",&a[i].x,&a[i].y);
    double Min = 0x7fffffff;
    for(int i = 1;i <= n;++ i)
        for(int j = i + 1;j <= n;++ j)
            Min = min(Min,sqrt((a[i].x -a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y)));
    printf("%.4lf\n",Min);
    return 0;
}