首页 > 试题广场 >

给出二维平面上的n (n<=10000) 个点 (xi

[问答题]
给出二维平面上的n (n<=10000) 个点 (xi,yi) (i=1,2...n) (1<=xi<=100000, 1<=yi<=100000)，每个点的 xi 都是不一样的。按照 xi 的从小到大的顺序依次连接每个点，与 x 轴构成一个包围的区域，称为“包围度”，如下图红色区域。

如果你可以任意交换所有点的y 值，请设计一种算法使“包围度”最大。请用文字或者伪代码描述你的算法，输出最大的“包围度”（注意算法的时空复杂度）。


添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

酷家乐 算法工程师 2020
上传者：小小
难度：
0条回答 590浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号