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

Question

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

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

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

Answer 1

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

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;
}