在Python中找出两个点之间不存在点且最宽的垂直区域的面积

在Python中找出两个点之间不存在点且最宽的垂直区域的面积

假设我们有 n 个点 (x, y)。垂直区域是沿 y 轴无限延伸的区域。我们需要找出两个点之间不存在其他点并且是最宽的垂直区域的面积。

因此,如果输入为 pts = [[10,9],[11,11],[9,6],[11,9]],则输出为 1。

在Python中找出两个点之间不存在点且最宽的垂直区域的面积

红色和蓝色区域是最优的,其内部没有点。

要解决此问题,我们将按照以下步骤操作:

  • 对 pts 列表进行排序。

  • 对于 i 在范围从 1 到 pts 的长度,执行以下操作:

    • 返回 (pts[i, 0] – pts[i – 1, 0]) 的最大值。

示例

下面是 Python 代码实现,以获得更好的理解。

def solve(pts):
   pts.sort()
   return max(pts[i][0] - pts[i - 1][0] for i in range(1, len(pts)))
print(solve([[10,9],[11,11],[9,6],[11,9]]))

输入

[[10,9],[11,11],[9,6],[11,9]]

输出

1

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程