gpt4 book ai didi

algorithm - 计算被两条垂直线切割的水平线段

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

<分区>

给定 N 条具有起点和终点(即 A 和 B)的水平线段,对重叠条件没有限制。这意味着我们有从 (A,0) 到 (B,0) 的线段。现在我们可以画两条穿过这些线的垂直线。我们需要找到这两条线可以交叉的最大线段。(如果垂直线接触到任何水平线段,它也被计算在内)

示例:假设我们有 5 条线段:

2 3
1 3
1 5
3 4
4 5

然后我们将画两条线(平行于 Y 轴)在点 2 和点 4 处穿过 X 轴。这两条线将接触所有五个线段。所以答案是 5。

但是假设我们有 3 个线段:

1 2
3 4
5 6

那么答案是 2,因为在这种情况下不能触摸超过两个点。

如何解决这个问题?请帮忙。

注1≤N≤10^5和0≤A < B≤10^9

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