[Luogu1429]平面最近点对(加强版)
2024-10-20 08:24:16
题目大意:
平面最近点对。
思路:
分治。
首先将所有点排序
每次把当前区间分为两半,递归求解两个区间内部的情况,然后枚举区间两边的点。
#include<cmath>
#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
typedef std::pair<double,double> Point;
const int N=;
Point p[N];
int num[N];
double ans=1e10;
inline double sqr(const double &x) {
return x*x;
}
inline double dis(const Point &a,const Point &b) {
return sqrt(sqr(std::abs(a.first-b.first))+sqr(std::abs(a.second-b.second)));
}
void solve(const int &l,const int &r) {
if(l==r) return;
const int mid=(l+r)/;
solve(l,mid);`
solve(mid+,r);
num[]=;
for(register int i=mid+;i<=r;i++) {
if(p[i].first-p[mid].first<ans) {
num[++num[]]=i;
}
}
for(register int i=l;i<=mid;i++) {
if(p[mid].first-p[i].first<ans) {
for(register int j=;j<=num[];j++) {
ans=std::min(ans,dis(p[i],p[num[j]]));
}
}
}
}
int main() {
const int n=getint();
for(register int i=;i<n;i++) {
scanf("%lf%lf",&p[i].first,&p[i].second);
}
std::sort(&p[],&p[n]);
solve(,n-);
printf("%.4f\n",ans);
return ;
}
最新文章
- JS和JSON的区别
- java多线程编程
- Page传回页面的值问题
- oracle索引使用时注意
- Delphi For Android 开发笔记-附:如何Delphi中同时实现Windows、Android版的GetModuleFileName函数
- 自动化运维——一键安装MySQL
- (原)配置vs2013使用intel的IPP库
- awk详解 数组
- Eclipse从数据库逆向生成Hibernate实体类和映射文件(Eclipse插件系列之HibernateTools)
- 大战Java虚拟机【3】—— 类加载机制
- post传递中文时,可以使用urlEncode编码进行转码
- Golang之发送消息至kafka
- IDEA与Eclipse
- vue2.0项目中 localhost改成ip地址访问
- PC/FORTH 循环
- Quart2D矩阵变换
- JDK5新特性之 可变参数的方法
- Istio全景监控与拓扑
- Hibernate中的Session缓存问题
- extjs [1]