hdu 1007 Quoit Design(平面最近点对)
2024-09-08 15:08:34
题意:求平面最近点对之间的距离
解:首先可以想到枚举的方法,枚举i,枚举j算点i和点j之间的距离,时间复杂度O(n2).
如果采用分治的思想,如果我们知道左半边点对答案d1,和右半边点的答案d2,如何求跨两边点之间的答案呢?显然只用枚举中线两边d=min(d1,d2)范围的点,并且每个点都只需要枚举上下范围在d以内的点,显然这样的点不会很多。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <map>
using namespace std;
typedef long long ll;
const double inf=1e20;
const int maxn=; struct Point{
double x, y;
}point[maxn]; int n, mpt[maxn]; //以x为基准排序
bool cmpxy(const Point &a,const Point &b){
if(a.x!=b.x)
return a.x<b.x;
return a.y<b.y;
} bool cmpy(const int &a,const int &b){
return point[a].y<point[b].y;
} double min(double a,double b){
return a<b?a:b;
} double dis(int i,int j){
return sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x) + (point[i].y - point[j].y)*(point[i].y - point[j].y));
} double Closest_Pair(int left, int right){
double d=inf;
if(left==right)
return d;
if(left+==right)
return dis(left,right);
int mid=(left+right)>>;
double d1=Closest_Pair(left,mid);
double d2=Closest_Pair(mid+,right);
d=min(d1,d2);
int i,j,k=;
//分离出宽度为d的区间
for(i=left;i<=right;i++){
if(fabs(point[mid].x-point[i].x)<=d)
mpt[k++]=i;
}
sort(mpt,mpt+k,cmpy);
//线性扫描
for(i=;i<k;i++){
for(j=i+;j<k&&point[mpt[j]].y-point[mpt[i]].y<d; j++){
double d3=dis(mpt[i],mpt[j]);
if(d>d3)d=d3;
}
}
return d;
} int main(){
while(scanf("%d",&n)!=EOF){
if(n==)break;
for(int i=;i<n;i++)
scanf("%lf%lf",&point[i].x,&point[i].y);
sort(point,point+n,cmpxy);
printf("%.2lf\n",Closest_Pair(,n-)/);
}
return ;
}
最新文章
- 两个NOI题目的启迪8皇后和算24
- xcode 插件之KSImageNamed-Xcode
- [Hive - LanguageManual] Archiving for File Count Reduction
- C++ Primer Plus(第6版)中文版——课后练习程序代码
- JavaSE学习总结第19天_IO流1
- 看看微软代码的水平——Windows Live Writer 完成开源并推出开源分支
- 04-Foundation-NSSet、NSDictionary、block
- runloop和runtime
- Excel 一键上传到数据库
- Java的栈和队列
- [LeetCode] Number Complement 补数
- LCD接口和RGB介绍【转】
- C++智能指针剖析(上)std::auto_ptr与boost::scoped_ptr
- [python]Generators
- C++类型转换的注意事项
- opengl摄像机
- CentOS 下tomcat安装
- modprobe lsmod
- SSH 学习记录及在SSH模式下使用XShell连接服务器
- J2EE开发实战基础系列之开卷有益
热门文章
- Python原来这么好学-2.1节: 选择PyCharm作为开发工具
- Android Studio安装虚拟机步骤
- 多线程笔记 - provider-consumer
- 使用jquery封装的动画脚本(无动画、css3动画、js动画)
- Vue.js 从源码理解v-for和v-if的优先级的高低
- [红日安全]Web安全Day2 - XSS跨站实战攻防
- Apache Log4j 反序列化代码执行(CVE-2019-17571) 漏洞分析
- Android中ProgressBar的使用-通过Handler与Message实现进度条显示
- pip 自己的源 搭建
- POST注入之sqlmap