摘要：
标题描述P是给定的二维平面整数点集。定义P中的点x。如果x满足P中的任何点不在x的右上区域，则称为“最大值”。找到所有“最大”点的集合。
题目描述
P为给定的二维平面整数点集。定义 P 中某点x，如果x满足 P 中任意点都不在 x 的右上方区域内（横纵坐标都大于x），则称其为“最大的”。求出所有“最大的”点的集合。（所有点的横坐标和纵坐标都不重复, 坐标轴范围在[0, 1e9) 内）
如下图：实心点为满足条件的点的集合。请实现代码找到集合 P 中的所有 ”最大“ 点的集合并输出。
例子：
input:
5
1 2
5 3
4 6
7 5
9 0
output:
4 6
7 5
9 0
代码实现
#!/usr/bin/env python # -*- encoding: utf-8 -*- class MaxPointDraw: def __init__(self): self.xy = [] self.max_x = 0 self.max_y = 0 def generateCoordinateCollection(self): number = int(input('please input a number(1 <= number <= 10000):')) for i in range(number): input_xy = input() x = int(input_xy.split(' ')[0]) y = int(input_xy.split(' ')[1]) if x > self.max_x: self.max_x = x if y > self.max_y: self.max_y = y self.xy.append([x, y]) def checkIsMaxPoint(self, xy_args): x = xy_args[0] y = xy_args[1] for xy_list in self.xy: x_value = xy_list[0] y_value = xy_list[1] if x_value > x and y_value > y: return False return True def Output(self): print('--------------------') for xy_list in self.xy: x_value = xy_list[0] y_value = xy_list[1] if self.checkIsMaxPoint(xy_list): print(' '.join(['%s'%xy for xy in xy_list])) if __name__ == "__main__": mpd = MaxPointDraw() mpd.generateCoordinateCollection() mpd.Output()
输出：
please input a number(1 <= number <= 10000):5
1 2
5 3
4 6
7 5
9 0
--------------------
4 6
7 5
9 0拓展
使用matplotlib来展示效果，以及随机生成一个点集合：
#!/usr/bin/env python # -*- encoding: utf-8 -*- from random import randint import matplotlib.pyplot as plt class MaxPointDraw: def __init__(self): self.xy = [] self.max_x = 0 self.max_y = 0 # generate CoordinateCollection def generateCoordinateCollection(self): number = int(input('please input a number(1 <= number <= 10000):')) for i in range(number): x = randint(0, number) y = randint(0, number) if x > self.max_x: self.max_x = x if y > self.max_y: self.max_y = y self.xy.append([x, y]) # check the point is Max or not def checkIsMaxPoint(self, xy_args): x = xy_args[0] y = xy_args[1] for xy_list in self.xy: x_value = xy_list[0] y_value = xy_list[1] if x_value > x and y_value > y: return False return True # show the MaxPoint result def DrawPaint(self): fig = plt.figure() ax = fig.add_subplot(111) ax.set(xlim=[0, self.max_x+self.max_x//2], ylim=[0, self.max_y+self.max_y//2], title='Max Point Set', ylabel='Y-Axis', xlabel='X-Axis') for xy_list in self.xy: x_value = xy_list[0] y_value = xy_list[1] if self.checkIsMaxPoint(xy_list): plt.scatter([x_value], [y_value], color='red') else: plt.scatter([x_value], [y_value], color='blue') plt.show() if __name__ == "__main__": mpd = MaxPointDraw() mpd.generateCoordinateCollection() mpd.DrawPaint()
input1:
please input a number(1 <= number <= 10000):10
result1:
input2:
please input a number(1 <= number <= 10000):50
output2:
效果就是上面的样子，复制代码后运行前需要pip install matplotlib 不然会找不到这个包。