算法题目——最短路径问题(HDU—1007)

叁歲伎倆 2022-09-14 02:20 94阅读 0赞

题目链接：[HDU-1007][]

前序： 先看一维中的最短路径的计算方式

问题的简单描述：(题意)  
在一个笛卡尔系中，n个点分布不一，在这N个点中，求出相距最短的两个点之间的距离

思路：  
分治二分法  
解题报告：  
就是要把N个点x坐标和Y坐标进行排序，然后进行比较！  
代码过程：  
使用递归分治法解决问题  
递归的退出条件：仅当剩余两个顶点时，直接计算出距离。仅剩三个点时，求出任意两点之间的距离，进行比较  
进行分治递归：二分法，先将结构体数组分成两份（根据中间点来分）然后递归求d=min(左边s1，右边s2)  
点对分别在集合S1和S2中。利用递归分析法分别计算前两种情况，第三种方法另外分析。求解出三类子情况后，  
再合并三类情况，比较分析后输出三者中最小的距离。

参考代码：

#include <cstdio>
    #include <algorithm>
    #include<vector>
    #include <cmath>
    
    using namespace std;
    
    int n;
    struct node{
        
    	double x,y;
    }a[100001];
    
    int b[100001];
    
    double Min(double a,double b)
    {
        
    	return a<b?a:b;
    } 
     
    bool cmpx(node a,node b)
    {
        
    	return a.x<b.x;
    }
    
    bool cmpy(int A,int B)
    {
        
    	return a[A].y<a[B].y;
    }
    
    double Distance(node a,node b)
    {
        
    	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    }
    
    //参数：s 是结构体数组的开始(0)，e是结构体数组的长度(n-1) 
    double closestPoint(int s,int e)//求得是直径 
    {
        
    	if(e-s==1)//仅有两个点时 
    	 return Distance(a[s],a[e]);//求得是直径 
    	if(e-s==2)//仅三个点时 
    	 return Min(Distance(a[s],a[s+1]),Min(Distance(a[s+1],a[e]),Distance(a[s],a[e])));
    	
    	
    	int mid=(s+e)/2;
    	int index=0;
    	double d=Min(closestPoint(s,mid),closestPoint(mid+1,e));//分成前面一段，后面一段 得到最小直径 
    	
    	for(int i=s;i<=e;i++)
    	{
        
    		if(a[i].x>=a[mid].x-d&&a[i].x<=a[mid].x+d)//即当有一个点到中间结点的距离小于两段最短距离d时
    		//至少是直角边小于d，才有可能斜边有机会出现小于d 
    		 b[index++]=i;//记录的下标 
    	}
    	
    	sort(b,b+index,cmpy);//将记录的下标数据按照Y轴进行排序 
    	//有个原理说明了这个下标序列最多有六个点 
    	for(int i=0;i<index;i++)
    	{
        
    		for(int j=i+1;j<index&&j<=i+7;j++)//因为最多有6个点，又因为结构体的起点是从1开始的 
    		{
        
    			if(a[b[j]].y-a[b[i]].y>=d)//如果y轴，该结点到中间结点的距离大于d时 
    			 break;
    			d=Min(d,Distance(a[b[i]],a[b[j]]));//如果y轴，该结点到中间结点的距离小于d时 
    		}
    	}
    	return d;
    }
    
    int main()
    {
        
    	vector<double> vec;
    	while(scanf("%d",&n)!=EOF&&n!=0)
    	{
        
    		for(int i=0;i<n;i++)
    		 scanf("%lf%lf",&a[i].x,&a[i].y);
    		
    		sort(a,a+n,cmpx);
    		vec.push_back(closestPoint(0,n-1)/2.0);
    		
    	}
    	for(int i=0;i<vec.size();i++)
    	{
        
    		printf("%.2lf\n",vec[i]);
    	}
    	
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oiR5Lus5LiN55Sf5Lqn5Luj56CB77yM5Y-q5piv5Luj56CB55qE5pCs6L-Q5bel_size_8_color_FFFFFF_t_70_g_se_x_16]

[HDU-1007]: https://acm.hdu.edu.cn/showproblem.php?pid=1007
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oiR5Lus5LiN55Sf5Lqn5Luj56CB77yM5Y-q5piv5Luj56CB55qE5pCs6L-Q5bel_size_8_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/1942d514c11443bbbe28fadbd3e46c07.png