狗面经

这题好难啊...我觉得是分两步做:
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
你好，请问什么叫做凸包呢？

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