狗面经

面试 阿三姐

题目 二维坐标系给一堆点

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

基本没有提示。。

这题好难啊...我觉得是分两步做:
1 找到这个点的集合的凸包.比较容易理解的方法可以用O(nlogn)找到n个点的凸包.
2 找到覆盖个凸包的最小的矩形.看wiki上有个定理是说最小覆盖的矩形一定和凸包的某一条边重合.这样的话只需要枚举一遍凸包的每条边就能确定,复杂度O(n).
综上,两步可以以O(nlogn)找到点的集合的最小矩形覆盖.

dawskiper 发表于 2017-11-6 21:42
这题好难啊...我觉得是分两步做:
1 找到这个点的集合的凸包.比较容易理解的方法可以用O(nlogn)找到n个点的 ...

你好，请问什么叫做凸包呢？

angiehoo 发表于 2017-11-10 04:41
你好，请问什么叫做凸包呢？

凸包就是能包含所有点的最小的凸多边形.

握草怎么这么难。。。。btw楼主你什么时候OA的？？求一波面经。。

今天的？谢谢LZ分享！

patpat 我面google是个三哥 我除了他的名字什么都没听懂 好在他直接把题目贴在google doc里了

patpat 感谢楼主分享！ 能请问矩形是由点围成四条边的么？还是四个角呢？

今天的面经 就给很多个点 问你最小的矩形（由四个点（x,y) 构成）的面积

请问矩形是要囊括所有的点吗？

YHYbrilliant123 发表于 2017-11-4 23:52
请问矩形是要囊括所有的点吗？

应该是不需要

请问楼主只考虑与坐标轴平行的矩形吗？

Wokao 都什么题