狗店

bc2615 发表于 2018-11-12 05:32
请问二分法在这里是怎么用的 可以详细说说吗

还有怎么保证rect边和坐标轴平行的问题。。。求指点

wilqud 发表于 2018-11-12 12:37
直接算xy差值的话怎么保证rect边和坐标轴平行呢。。。想不通求解释

其实很简单。
就是确定两个点。根据其y轴坐标去二分查找确定其他两个点，meanwhile update max so far.

枚举对角线就行了 可以唯一确定矩形

foryousee 发表于 2018-11-10 05:33
按照x值排序，x相同就排序y，然后二分法找出两两x之间的最小y值差，更新最小值。时间复杂度，排序O(nlogn) ...

这种方式不能保证找到4个点组成平行于xy轴的矩形吧，是不是用n2枚举两个点做对角线找其余两个点比较合理。

dengzeyu147 发表于 2018-11-9 20:52
楼主觉得这样做可以吗？
**** 本内容被作者隐藏 ****

这种做法点数是N，时间复杂度N^2，空间复杂度N^2，N在这里不是矩阵边长了，这种做法利口750会超时

foryousee 发表于 2018-11-10 05:33
按照x值排序，x相同就排序y，然后二分法找出两两x之间的最小y值差，更新最小值。时间复杂度，排序O(nlogn) ...

请问整体复杂度是多少呢？

请问楼主， 是这道题吗？https://leetcode.com/problems/minimum-area-rectangle/
谢谢！

maomao12 发表于 2018/11/29 10:16:04
请问楼主， 是这道题吗？https://leetcode.com/problems/minimum-area-rectangle/
谢谢！

是的，然后return的是四个顶点坐标
这题啥时候出的啊(;???Д??`)

吟游诗人刘小翠 发表于 2018-11-29 11:00
是的，然后return的是四个顶点坐标
这题啥时候出的啊(;???Д??`)

上两次contest