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

· · 题解

写题解写题解

step1：暴力

对于两个点i，j，计算dis（i，j），然后取最小值。

代码（100分，1.26s）：

#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
    long double x,y;
}a[200010];
double ans=10000000.0;
double dis(double a,double b,double c,double d){
    return sqrt(abs(c-a)*abs(c-a)+abs(d-b)*abs(d-b));
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            ans=min(ans,dis(a[i].x,a[i].y,a[j].x,a[j].y));
    printf("%.4lf",ans);
    return 0;
}

step2：排序优化

按照x关键字排序，计算min（ans，dis（i，i-1）） 代码（70分，53ms）：

#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
    long double x,y;
}a[200010];
double ans=10000000.0;
double dis(double a,double b,double c,double d){
    return sqrt(abs(c-a)*abs(c-a)+abs(d-b)*abs(d-b));
}
bool cmp(node a,node b){return (a.x==b.x)?(a.y<b.y):(a.x<b.x);}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp);
    for(int i=2;i<=n;i++)ans=min(ans,dis(a[i].x,a[i].y,a[i-1].x,a[i-1].y));
    printf("%.4lf",ans);
    return 0;
}

（？？？）

step3:玄学排错1

按照x关键字排序，计算min（ans，dis（i，i-1））和min（ans，dis（i，i-2）） 代码（100分，44ms）：

#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
    long double x,y;
}a[200010];
double ans=10000000.0;
double dis(double a,double b,double c,double d){
    return sqrt(abs(c-a)*abs(c-a)+abs(d-b)*abs(d-b));
}
bool cmp(node a,node b){return (a.x==b.x)?(a.y<b.y):(a.x<b.x);}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp);
    for(int i=2;i<=n;i++)ans=min(ans,dis(a[i].x,a[i].y,a[i-1].x,a[i-1].y));
    for(int i=3;i<=n;i++)ans=min(ans,dis(a[i].x,a[i].y,a[i-2].x,a[i-2].y));
    printf("%.4lf",ans);
    return 0;
}

（？？？？？？？）

step4:玄学排错2

按照x关键字排序，计算min（ans，dis（i，i-1））

按照y关键字排序，计算min（ans，dis（i，i-1））

代码（100分，48ms）：

#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
    long double x,y;
}a[200010];
double ans=10000000.0;
double dis(double a,double b,double c,double d){
    return sqrt(abs(c-a)*abs(c-a)+abs(d-b)*abs(d-b));
}
bool cmp(node a,node b){return (a.x==b.x)?(a.y<b.y):(a.x<b.x);}
bool cmp1(node a,node b){return (a.y==b.y)?(a.x<b.x):(a.y<b.y);}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp);
    for(int i=2;i<=n;i++)ans=min(ans,dis(a[i].x,a[i].y,a[i-1].x,a[i-1].y)); 
    sort(a+1,a+n+1,cmp1);
    for(int i=2;i<=n;i++)ans=min(ans,dis(a[i].x,a[i].y,a[i-1].x,a[i-1].y));
    printf("%.4lf",ans);
    return 0;
}

（ooo）

step5：玄学优化*2

按照x关键字排序，计算min（ans，dis（i，i-1））和min（ans，dis（i，i-2））和min（ans，dis（i，i-3））（你无聊吗？）

代码（100分，52ms）：

#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
    long double x,y;
}a[500010];
double ans=10000000.0;
double dis(double a,double b,double c,double d){
    return sqrt(abs(c-a)*abs(c-a)+abs(d-b)*abs(d-b));
}
bool cmp(node a,node b){return (a.x==b.x)?(a.y<b.y):(a.x<b.x);}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp);
    for(int i=2;i<=n;i++)ans=min(ans,dis(a[i].x,a[i].y,a[i-1].x,a[i-1].y));
    for(int i=3;i<=n;i++)ans=min(ans,dis(a[i].x,a[i].y,a[i-2].x,a[i-2].y));
    for(int i=4;i<=n;i++)ans=min(ans,dis(a[i].x,a[i].y,a[i-3].x,a[i-3].y));
    printf("%.4lf",ans);
    return 0;
}

(666666……)