本文主要是介绍Quoit Design HDU - 1007，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=1007
一直觉得算法课水 但还是有点东西的 连最近点对问题都没遇到过 乍看之下还没什么思路 滚来补题
思路就是课本上那些东西 细节详见注释
提交要加上多组 再把答案除2
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;struct node
{double x,y;
};node point[maxn],tmp[maxn];
double pre[maxn];
int lef[maxn],rgt[maxn],pos[maxn];
int n;bool cmp(node n1,node n2)
{return n1.x<n2.x;
}double getdis(node u,node v)
{return sqrt((u.x-v.x)*(u.x-v.x)+(u.y-v.y)*(u.y-v.y));
}double solve(int l,int r)
{double dis,res;int m,p,q,i,j;if(l+1==r){if(point[l].y>point[r].y) swap(point[l],point[r]);//为了保证y有序return getdis(point[l],point[r]);}if(l+2==r){if(point[l].y>point[l+1].y) swap(point[l],point[l+1]);//为了保证y有序if(point[l+1].y>point[r].y){swap(point[l+1],point[r]);if(point[l].y>point[l+1].y) swap(point[l],point[l+1]);}return min(getdis(point[l],point[l+1]),min(getdis(point[l+1],point[r]),getdis(point[r],point[l])));}m=(l+r)/2;dis=min(solve(l,m),solve(m+1,r));p=0,q=0;for(i=l;i<=r;i++){//pre[m]即为[l,r]区间内所有点的x坐标的中位数if(pre[m]-dis<=point[i].x&&point[i].x<=pre[m]) lef[++p]=i,pos[p]=q;//该点在x=pre[m]这条直线的左边 pos[p]即为在x=pre[m]这条直线的右边的所有点中y坐标第一个小于等于该点的点else if(pre[m]<=point[i].x&&point[i].x<=pre[m]+dis) rgt[++q]=i;//该点在x=pre[m]这条直线的右边}res=dis;for(i=1;i<=p;i++){//对x=pre[m]这条直线左边每个点 找x=pre[m]这条直线右边哪些点与其纵坐标之差在合理范围内 因已求出pos[i]所以复杂度可以降到0(c*n)for(j=pos[i];j>=1;j--){if(point[lef[i]].y-point[rgt[j]].y>=dis) break;//超出范围res=min(res,getdis(point[lef[i]],point[rgt[j]]));}for(j=pos[i]+1;j<=q;j++){if(point[rgt[j]].y-point[lef[i]].y>=dis) break;//超出范围res=min(res,getdis(point[lef[i]],point[rgt[j]]));}}p=l,q=m+1,i=l;//为了保证y有序 归并处理while(p<=m&&q<=r){if(point[p].y<point[q].y) tmp[i++]=point[p++];else tmp[i++]=point[q++];}while(p<=m) tmp[i++]=point[p++];while(q<=r) tmp[i++]=point[q++];for(i=l;i<=r;i++) point[i]=tmp[i];return res;
}int main()
{int i;scanf("%d",&n);for(i=1;i<=n;i++) scanf("%lf%lf",&point[i].x,&point[i].y);sort(point+1,point+n+1,cmp);//分治x 处理yfor(i=1;i<=n;i++) pre[i]=point[i].x;//为了找中位数printf("%.2f\n",solve(1,n));return 0;
}
这篇关于Quoit Design HDU - 1007的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
