基础款，暴力可过。
正常款，玄学版本也能过（题解第一个做法，不过最初没卡这种方法的话应该随机情况下能过绝大多数点）。
分治解决，将集合每次分成两部分，两个部分本别先求出集合内部的最小点对的答案 d；然后找到 mid 将这个集合划分成两部分，先按照一维排序并只保留离这个划分线距离不超过 d 的。
然后按照另一维排序，枚举处理。
实际上就有很多剪枝了。sort 排序的程序复杂度是 \(O(n \log^2 n)\)，分治排序的程序复杂度是严格 \(O(n \log n)\) 的。
我不会证明复杂度，但题解区有写的很好的证明博客。请大家移步去看。
Code:
#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=1e6+10;
int n;
int t[N];
struct node{int x,y;}s[N];
db dis(int p,int q){
int ax=s[p].x,ay=s[p].y;
int bx=s[q].x,by=s[q].y;
return sqrt(1.0*(ax-bx)*(ax-bx)+1.0*(ay-by)*(ay-by));
}
bool cmp(node a,node b){
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
bool cmp2(int a,int b){
return s[a].y<s[b].y;
}
db mer(int l,int r){
db d=1e18;
if(l==r) return d;
if(l+1==r) return dis(l,r);
int mid=(l+r)>>1;
db d1=mer(l,mid),d2=mer(mid+1,r);
d=min(d1,d2);
int k=0;
for(int i=l;i<=r;i++)
if(fabs(s[mid].x-s[i].x)<d) t[++k]=i;
sort(t+1,t+k+1,cmp2);
for(int i=1;i<=k;i++){
for(int j=i+1;j<=k;j++){
if(s[t[j]].y-s[t[i]].y>=d) break;
d=min(d,dis(t[i],t[j]));
}
}
return d;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&s[i].x,&s[i].y);
sort(s+1,s+n+1,cmp);
printf("%.4lf",mer(1,n));
return 0;
}
实际上和上题的区别只是卡掉了那个玄学做法。
点击查看代码
#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=1e6+10;
int n;
int t[N];
struct node{int x,y;}s[N];
db dis(int p,int q){
int ax=s[p].x,ay=s[p].y;
int bx=s[q].x,by=s[q].y;
return sqrt(1.0*(ax-bx)*(ax-bx)+1.0*(ay-by)*(ay-by));
}
bool cmp(node a,node b){
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
bool cmp2(int a,int b){
return s[a].y<s[b].y;
}
db mer(int l,int r){
db d=1e18;
if(l==r) return d;
if(l+1==r) return dis(l,r);
int mid=(l+r)>>1;
db d1=mer(l,mid),d2=mer(mid+1,r);
d=min(d1,d2);
int k=0;
for(int i=l;i<=r;i++)
if(fabs(s[mid].x-s[i].x)<d) t[++k]=i;
sort(t+1,t+k+1,cmp2);
for(int i=1;i<=k;i++){
for(int j=i+1;j<=k;j++){
if(s[t[j]].y-s[t[i]].y>=d) break;
d=min(d,dis(t[i],t[j]));
}
}
return d;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&s[i].x,&s[i].y);
sort(s+1,s+n+1,cmp);
printf("%.0lf",pow(mer(1,n),2));
return 0;
}
求最近的三个点。
和上面差不多，只是确定了划分线后，只保留 fabs(s[mid].x-s[i].x)<ans/2.0 的部分。
#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=1e6+10;
int n;
int t[N];
struct node{int x,y;}s[N];
db ans=1e18;
db dis(int p,int q){
int ax=s[p].x,ay=s[p].y;
int bx=s[q].x,by=s[q].y;
return sqrt(1.0*(ax-bx)*(ax-bx)+1.0*(ay-by)*(ay-by));
}
bool cmp(node a,node b){
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
bool cmp2(int a,int b){
return s[a].y<s[b].y;
}
void mer(int l,int r){
if(l==r) return;
int mid=(l+r)>>1;
mer(l,mid),mer(mid+1,r);
int k=0;
for(int i=l;i<=r;i++)
if(fabs(s[mid].x-s[i].x)<ans/2.0) t[++k]=i;
sort(t+1,t+k+1,cmp2);
for(int i=1;i<=k;i++){
for(int j=i+1;j<=k;j++){
if(s[t[j]].y-s[t[i]].y>=ans/2.0) break;
for(int q=j+1;q<=k;q++){
if(s[t[q]].y-s[t[i]].y>=ans/2.0) break;
ans=min(ans,dis(t[i],t[j])+dis(t[i],t[q])+dis(t[q],t[j]));
}
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&s[i].x,&s[i].y);
sort(s+1,s+n+1,cmp);
mer(1,n);
printf("%.6lf",ans);
return 0;
}
第一节课喝了很凉的水，因为接的热水很少；第二节课长记性了，接了一杯子热水；
然后一节课没喝上水；