Smallest Enclosing Rectangle of some points id 2D plane where the number of points is 100000. The points will not be collinear. I need some idea to solve the problem.
Thanks.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Smallest Enclosing Rectangle of some points id 2D plane where the number of points is 100000. The points will not be collinear. I need some idea to solve the problem.
Thanks.
Name |
---|
I suppose that smallest rectangle would necessary have at least one of sides which contains at least two of points on it (and other sides would have at least one point each).
So you may start with searching for convex hull for this set. One of its bordering line would be the same as one of the required rectangle's side. You are just to check each of the hull borders, build minimal rectangle upon it and select minimum of all these rectangles. Though I suppose that you may need to optimize series rectangle building so that if convex hull have M points, you build M rectangles in O(M), not O(N*M).
Thanks a lot RodionGork. I am trying.
- proposed algorithm is wrong;
- your implementation is not correct.
Does it work correctly for proposed testcase?
Thanks again for trying to help me. I saw the same problem before and tried. There may be a way called Rotating calipers . But I have no idea abut that.
Can any one give me some new idea to solve this problem?
You can do the following: