题解 P1429 【平面最近点对（加强版）】

白菜道士 · 2019-07-11 11:01:44 · 题解

关于这道题，其实是比较玄学的

思路很简单（简直就是暴力中的极品）

不知道为什么dalao们说要随机旋转

我基本上纯暴力A掉了

以下为方法：

先求第1个点与其余n-1个点的距离；

再求第2个点与其余n-2个点的距离；

…………………………………………

再求第n-1个点与其余1个点的距离；

然后找出最小值，如此的算法复杂度为O(n^2)

核心代码如下：

  for(int i=1; i<=n; i++)
        for(int j=i; j<=n; j++)
            if(i+j<=n)
            {
                d=sqrt((x[i]-x[j])*(x[i]-x[j])*1.0+(y[i]-y[j])*(y[i]-y[j])*1.0);
                if(d<mindist)   mindist=d;
            }

显然不行

然后就比较玄学了

为了减少枚举量，本少决定只比较每个点后面的150个点

然后莫名AC了

为了再次减少枚举量，本少决定只比较每个点后面的50个点

然后再次莫名AC了

为了再次减少枚举量，本少决定只比较每个点后面的3个点

然后再次莫名AC了

这是一个玄学问题

AC代码如下

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;//流线型头文件

const int Max=200010;
double x[Max],y[Max];

void Qsort(int l,int r)
{
    int i,j;
    double a,b;
    i=l;
    j=r;
    a=x[(l+r)/2];
    while(i<=j)
    {
        while(x[i]<a)   i++;
        while(a<x[j])   j--;
        if(i<=j)
        {
            b=x[i]; x[i]=x[j]; x[j]=b;
            b=y[i]; y[i]=y[j]; y[j]=b;
            i++;
            j--;
        }
    }
    if(i<r) Qsort(i,r);
    if(l<j) Qsort(l,j);
}//先给x坐标排序

int main()
{
    int len;
    scanf("%d",&len);
    for(int i=1; i<=len; i++)
        scanf("%lf%lf",&x[i],&y[i]);
    double mindist=99999999999;
    Qsort(1,len);
    double d;
    for(int i=1; i<=len; i++)
        for(int j=1; j<=3; j++)//比较每个点后面的3个点
            if(i+j<=len)
            {
                d=sqrt((x[i]-x[i+j])*(x[i]-x[i+j])*1.0+(y[i]-y[i+j])*(y[i]-y[i+j])*1.0);
                if(d<mindist)   mindist=d;
            }//比较
    printf("%.4lf\n",mindist);
    return 0;
}