首页 > 其他分享 >平面最近点对

平面最近点对

时间:2024-09-28 12:45:27浏览次数:6  
标签:return min int Point mid 最近 solve 平面

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5,inf=0x7f7f7f7f;
int n;
struct Point
{
    double x,y;
}a[N],t[N];
bool cmp1(Point A,Point B)
{
    if(A.x==B.x) return A.y<B.y;
    return A.x<B.x;
}
bool cmp2(Point A,Point B) 
{
    return A.y<B.y;
}
double dis(Point A,Point B)
{
    double x=B.x-A.x,y=B.y-A.y;
    return sqrt(x*x+y*y);
}
double solve(int l,int r)
{
    double d=inf;
    if(l==r) return d;
    if(l+1==r) return dis(a[l],a[r]);
    int mid=(l+r)>>1;
    d=min(solve(l,mid),solve(mid+1,r));
    int tot=0;
    for(int i=l;i<=r;i++)
        if(fabs(a[i].x-a[mid].x)<d)
            t[++tot]=a[i];
    sort(t+1,t+tot+1,cmp2);
    for(int i=1;i<tot;i++)
        for(int j=i+1;j<=tot;j++)
        {
            if(t[j].y-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("%lf%lf",&a[i].x,&a[i].y);
    sort(a+1,a+n+1,cmp1);
    printf("%.4lf",solve(1,n));
    return 0;
}

标签:return,min,int,Point,mid,最近,solve,平面
From: https://www.cnblogs.com/zhouruoheng/p/18437231

相关文章

  • 8,(经典面试题:分组求topN)Python数分之Pandas训练,力扣,1532. 最近的三笔订单
    学习:知识的初次邂逅复习:知识的温故知新练习:知识的实践应用目录一,原题力扣链接二,题干三,建表语句四,分析五,Pandas解答六,验证七,知识点总结一,原题力扣链接.-力扣(LeetCode)二,题干表:Customers+---------------+---------+|ColumnName|Type|+------......
  • 三维点云使用pcl实现RANSAC平面分割
    小白每日一练!点云分割分割是将点云划分为多个部分的过程,每个部分代表不同的物体或表面。在这里,我们使用RANSAC算法来识别和分离平面。(以ModelNet40为例)完整代码放在最后面啦!!测试好了可以直接使用!!RANSAC算法RANSAC算法是一种用于从一组包含异常数据的观测数据中估计数学模......
  • 最近公共祖先思考题
    #1有n个物品,每个物品有重量wi和体积vi且密度均匀。你可以切物品,每次可以选一个物品切成两部分,也就是选一个0到1的实数k把物品分成k和(1-k)比例的两个物品。你有最多X次切的机会。问题1.要想保证切完之后一定能把物品分成两组使得两组重量和相等,体积和也相等,X至少是几。ans1.......
  • 道歉贴,为最近写的一篇“垃圾贴”
    最近写了几篇阅读量高的文章,其实说到阅读量特别的高,我并怎么不高兴,到这里一定有人说,你装,装什么B!我写现在这篇文章的时候是2024年9月14日,显示的是这三篇文章,当时的阅读量,让我最不开心或者说郁闷的是第一篇,Oracle的那篇。Why,因为我自己认为,那篇文章垃圾,太垃圾了,我作......
  • 为什么多模态大语言模型最近用BLIP2中Q-Former结构的变少了?
    前言本篇介绍为什么多模态大语言模型(MLLM)最近的工作中用BLIP2中Q-Former结构的变少了?简单来说,相较于MLP的方案,即LLaVA-1.5,BLIP-2中的Q-Former模型在参数量上更为庞大,其收敛过程也相对缓慢。在同等条件下,Q-Former的性能并未达到LLaVA-1.5所展现出的卓越水平。值得注意的是,即使在数据......
  • python 比较两个或多个时间,获取最大的时间(最近的时间)
    自定义的公共函数importdate_timedefstr2datetime(date_time,form="%Y-%m-%d%H:%M:%S"):_datetime=datetime.datetime.strptime(date_time,form)ifisinstance(date_time,str)elsedate_timereturn_datetimedefdatetime2str(date_time,form=&q......
  • Day17 二叉树part07| LeetCode 235. 二叉搜索树的最近公共祖先 ,701.二叉搜索树中的插
    235.二叉搜索树的最近公共祖先235.二叉搜索树的最近公共祖先利用二叉搜索树的特性——有序树,可知,如果中间节点是p和q的公共节点,那个中间节点的数值一定在[p,q]区间因此,从根节点往下搜索,遇到的第一个位于[p,q]或[q,p]区间的节点就是最近公共祖先classSolution{......
  • leetcode刷题day19|二叉树Part07(235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的
    235.二叉搜索树的最近公共祖先思路:二叉搜索树首先考虑中序遍历。根据二叉搜索树的特性,如果p,q分别在中间节点的左右两边,该中间节点一定是最近公共祖先,如果在同一侧,则递归这一侧即可。递归三部曲:1、传入参数:根节点,p,q,返回节点。2、终止条件:因为p,q一定存在,所以不会遍历到......
  • Day16 二叉树part06| LeetCode 530.二叉搜索树的最小绝对差 ,501.二叉搜索树中的众数,23
    530.二叉搜索树的最小绝对差530.二叉搜索树的最小绝对差classSolution{publicList<Integer>res=newArrayList<>();voidtraversal(TreeNoderoot){if(root==null)return;traversal(root.left);......
  • 代码随想录算法训练营,9月16日 | 235. 二叉搜索树的最近公共祖先,701.二叉搜索树中的插
    235.二叉搜索树的最近公共祖先题目链接:235.二叉搜索树的最近公共祖先文档讲解︰代码随想录(programmercarl.com)视频讲解︰二叉搜索树的最近公共祖先日期:2024-09-16想法:相比于普通二叉树,二叉搜索树从上往下遍历,在qp中间的值的一定是公共祖先,而第一个则是最近,因为此时你在这个祖......