题解 P1257 【平面上的最接近点对】

· · 题解

【思路】

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

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

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