首页 > 代码库 > 【HDOJ】P1007 Quoit Design （最近点对）
【HDOJ】P1007 Quoit Design （最近点对）
题目意思很简单，意思就是求一个图上最近点对。
具体思想就是二分法，这里就不做介绍，相信大家都会明白的，在这里我说明一下如何进行拼合。
具体证明一下为什么只需要检查6个点
首先，假设当前左侧和右侧的最小值为d，那么对于一个点，如果有个最小值小于d，那么一定存在于上d下d左d右d的一块区域内，又因为是从左到右，从上到下，所以左侧的那部分匹配的区域会重叠，也就是对于左侧的区域，完全没有必要去进行匹配。所以只需要对右侧d，上下d的区域进行匹配，而假设这个区域内的所以点的距离为d那么最多为6个，那么如果长度小于d那么根据抽屉原理可以知道最多为6个。
#include <iostream>#include <algorithm>#include <cstdio>#include <cmath>#define MaxN 100001using namespace std;int N,t[MaxN],k;struct Posi{ double x,y;}point[MaxN];bool compoint(Posi a,Posi b){ return a.x!=b.x?a.x<b.x:a.y<b.y;}bool comp(int a,int b){ return point[a].y<point[b].y;}inline double dist(int a,int b){ return sqrt((point[a].x-point[b].x)*(point[a].x-point[b].x)+(point[a].y-point[b].y)*(point[a].y-point[b].y));}double solve(int l,int r){ if (l==r) return 1e30; if (l+1==r) return dist(l,r); int mid=(l+r)>>1; double ld=solve(l,mid); double rd=solve(mid+1,r); double d=min(ld,rd); k=0; for (int i=l;i<=r;i++) if (fabs(point[i].x-point[mid].x)<d) t[++k]=i; sort(t+1,t+k+1,comp); for (int i=1;i<k;i++) for (int j=i+1;j<=k && fabs(point[t[j]].y-point[t[i]].y)<d;j++){ double newd=dist(t[i],t[j]); if (newd<d) d=newd; } return d;}int main(){ while(cin>>N,N!=0){ for (int i=1;i<=N;i++) scanf("%lf%lf",&point[i].x,&point[i].y); sort(point+1,point+N+1,compoint); printf("%.2lf\n",solve(1,N)/2); } return 0;}
【HDOJ】P1007 Quoit Design （最近点对）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。