C++ 代码对比分析：两种实现星形图最远点对距离算法

本文对比分析了两种 C++ 代码实现星形图最远点对距离算法，分析了两种代码的差异，帮助你理解不同代码实现的优劣，以及代码的优化方向。

代码一:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 6e3 + 10;
const int INF = 0x3f3f3f3f;

struct Point
{
	ll x, y;
	bool operator<(Point other)
	{
		if (x == other.x)
		{
			return y < other.y;
		}
		return x < other.y;
	}
};

Point a[N];
int n, m, k, u;
ll dis[N];
ll ans;
bool vis[N];

ll square(ll x)
{
	return x * x;
}

ll len(int x, int y)
{
	if (x >= k || y >= k)
	{
		return abs(a[x].y - a[y].y);
	}
	return square(a[x].x - a[y].x) + square(a[x].y - a[y].y); 
}

int main()
{
//	freopen('starway.in','r',stdin);
//	freopen('starway.out','w',stdout);
	
scanf('%d%d%d', &n, &m, &k);
	for (int i = 0; i < k; i++)
	{
		scanf('%d%d', &a[i].x, &a[i].y);
	}
	
a[k].x = 0;
	a[k].y = m;
	a[k + 1].x = 0;
	a[k + 1].y = m;
	dis[k + 1] = INF;
	vis[u = k] = 1;
	
	for (int i = 0; i < k; i++)
	{
		dis[i] = len(k, i);
	}
	while (1)
	{
		printf('!');
		ll minn = 1ll * INF << 30;
		int mini;
		for (int i = 0; i < k + 2; i++)
		{
			if (!vis[i] && dis[i] < minn)
			{
				minn = dis[i];
				mini = i;
			}
		}
		if (mini = k + 1)
		{
			break;
		}
		ans = max(ans, minn);
		vis[u = mini] = 1;
		for(int i = 0; i < k + 2; i++)
		{
			ll x = len(i, u);
			if(!vis[i] && x < dis[i])
			{
				dis[i] = x;
			}
		}
	}

	printf('%.8lf', sqrt(ans) / 2.0);
	
	return 0;
}

代码二:

#include<bits/stdc++.h>
using namespace std;
void read(int &x)
{
	char ch=getchar();
	x=0;
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
}
int n,m,k;
const int K=6005,inf=0x3f3f3f3f;
int X[K],Y[K];
double len(int x,int y)
{
	if(x>k||y>k)
	{
		return abs(Y[x]-Y[y]);
	}
	return sqrt(pow(1ll*X[x]-X[y],2)+pow(1ll*Y[x]-Y[y],2));
}
int bz[K];
double dis[K];
double ans=0;
int u;
int main()
{
//	freopen('starway.in','r',stdin);
//	freopen('starway.out','w',stdout);
	read(n),read(m),read(k);
	for(int i=1; i<=k; i++)
	{
		read(X[i]),read(Y[i]);
		dis[i]=inf;
	}
	Y[k+1]=m;
	dis[k+2]=inf;
	bz[u=k+1]=1;
	for(int i=1; i<=k; i++)dis[i]=len(k+1,i);
	while(1)
	{
		printf('!');
		double min1=inf;
		int num;
		for(int i=1; i<=k+2; i++)if(!bz[i]&&dis[i]<min1)
			{
				min1=dis[i];
				num=i;
			}
		if(num==k+2)break;
		ans=max(ans,min1);
		bz[u=num]=1;
		for(int i=1; i<=k+2; i++)
		{
			double x=len(i,u);
			if(!bz[i]&&x<dis[i])dis[i]=x;
		}
	}
	printf('%.8lf',ans/2);
}

两份代码的差异如下：

数据结构选择：
- 第一份代码使用了结构体 Point 来表示坐标点，而第二份代码使用了两个数组 X 和 Y 分别存储 x 坐标和 y 坐标。
- 使用结构体 Point 可以将 x 和 y 坐标封装在一起，代码更加清晰易读；而使用数组 X 和 Y 可以节省内存空间，代码更加简洁高效。
距离计算方法：
- 第一份代码中的 len 函数计算两点之间的距离时，对于 k 之外的点直接返回 y 坐标的差值，而第二份代码使用了 sqrt 和 pow 函数来计算两点之间的距离。
- 第一份代码的 len 函数针对 k 之外的点进行特殊处理，提高了代码效率；而第二份代码使用 sqrt 和 pow 函数计算距离，代码更加通用，但效率略低。
数组下标：
- 第一份代码中的 dis 数组的下标范围是 0 到 k+1，而第二份代码中的 dis 数组的下标范围是 1 到 k+2。
- 两份代码的数组下标选择不同，主要是为了适应代码中其他变量的定义和使用。
标记方法：
- 第一份代码中的 vis 数组用来标记某个点是否被访问过，而第二份代码使用了 bz 数组来标记某个点是否被访问过。
- 两份代码的标记方法不同，都是为了方便在代码中判断某个点是否已经被访问过。
输入输出方式：
- 第一份代码中的输入方式使用了 scanf 函数，而第二份代码使用了自定义的 read 函数。
- 第一份代码使用了标准库函数 scanf 进行输入，代码更加简洁；而第二份代码使用了自定义的 read 函数，可以提高代码的效率，尤其是在输入数据量很大的情况下。
循环条件：
- 第一份代码中的循环条件是 while(1)，而第二份代码的循环条件是 while(1)。
- 两份代码的循环条件都是用来实现循环，直到满足某个条件为止。
输出格式：
- 第一份代码中的输出格式为 '%.8lf'，而第二份代码的输出格式为 '%.8lf'。
- 两份代码的输出格式相同，都是用来输出浮点数，并保留小数点后 8 位。

总结：

两份代码实现的功能相同，但代码的细节有所不同，例如数据结构选择、距离计算方法、数组下标、标记方法、输入输出方式等。开发者可以根据实际情况选择合适的代码实现方式。

希望本文对您理解两种 C++ 代码实现星形图最远点对距离算法有所帮助。如果您有任何问题或建议，欢迎留言讨论。')