gpt4 book ai didi

algorithm - 分而治之算法来计算 friend 点数

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:20:06 25 4
gpt4 key购买 nike

我有一个问题需要分而治之解决。有一个包含 N 个点的集合 S。如果有一个平行于轴的正方形,只包含S中的两个点p1和p2,则我们称p1和p2为 friend 点。

现在,我需要使用分而治之算法来计算 S 中有多少 friend 点。

我想了很久。我没有办法。我需要你的帮助。我的英语不好,如果你有问题,请问我,我会补充。谢谢。

最佳答案

伪代码中的以下(不一定是最优的)算法怎么样?

List<Pair<Point, Point>> findFriends(List<Point> points)
{
List<Pair<Point, Point>> friends = new List<Pair<Point, Point>>();

if (points.Count > 1)
{
if (points.Count == 2)
{
friends.Add(new Pair<Point, Point>(points[0], points[1]);
}
else
{
int xMedian = getMedianX(points);
int yMedian = getMedianY(points);
List<Point> topLeftPoints = selectPoints(points, 0, xMedian-1, yMedian, yMax);
List<Point> bottomLeftPoints = selectPoints(points, 0, xMedian-1, 0, yMedian-1);
List<Point> topRightPoints = selectPoints(points, xMedian, xMax, yMedian, yMax);
List<Point> bottomRightPoints = selectPoints(points, xMedian, xMax, yMedian, yMax);

friends.Add(findFriends(topLeftPoints));
friends.Add(findFriends(bottomLeftPoints));
friends.Add(findFriends(topRightPoints));
friends.Add(findFriends(bottomRightPoints));
}
}

return friends;
}

关于algorithm - 分而治之算法来计算 friend 点数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42921949/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com