最大点集

[编程题]最大点集

热度指数：4887 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

P为给定的二维平面整数点集。定义P中某点x，如果x满足P中任意点都不在x的右上方区域内（横纵坐标都大于x），则称其为“最大的”。求出所有“最大的”点的集合。（所有点的横坐标和纵坐标都不重复,坐标轴范围在[0, 1e9]内）

如下图：实心点为满足条件的点的集合。

请实现代码找到集合P中的所有”最大“点的集合并输出。

输入描述:

第一行输入点集的个数N， 接下来N行，每行两个数字代表点的X轴和Y轴。1 ≤ n ≤ 500000

输出描述:

输出“最大的”点集合， 按照X轴从小到大的方式输出，每行两个数字分别代表点的X轴和Y轴。

示例1

输入

输出

4 6
7 5
9 0

备注:

输出结果按照x轴排序

算法知识视频讲解

Python

冷遇"

def find():
    num = int(input())
    points = []
    result = []
    for i in range(num):
        x,y = map(int, input().split())
        points.append((x,y))
    points.sort()
    result.append(points[-1])
    target = points[-1][1]
    for i in range(num-2,-1,-1):
        if points[i][1] > target:
            target = points[i][1]
            result.insert(0,points[i])
    for i in range(len(result)):
        print(result[i][0],result[i][1])

if __name__ == "__main__":

find()

Python解题思路：首先不用考虑横纵坐标重合的情况下，将所有点排正序sort，那么最后一个点就是x坐标最大的点,将此点设为一个参照点。那么符合题目要求的点此时一定在参照点的左上方。然后一一倒序比对上一个点和参照点，把符合要求的点（即当前点y坐标大于参照点）保存到存放结果的数组中并设置成新的参照点。

发表于 2020-07-15 18:02:48 回复(1)