I think there will be at least two point on the convex hull. So first step I get the convex hull of given points. then run the O(n^3) algorithm but I get WA. Can you explain Why is it not correct?
# | 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 |
I think there will be at least two point on the convex hull. So first step I get the convex hull of given points. then run the O(n^3) algorithm but I get WA. Can you explain Why is it not correct?
Name |
---|
To get the right answer, it's necessary to check not only all pairs of points, but the triples too.
Upd. However, it's much easier to use gradient descend or ternary search.
I think when the circle surround the convex hull then it must surround all the point ,so I transform the initial ploblem to get the miniman circle which can surround the convex hull
I can get AC when run O(n^3) algorithm directly.
But sorry,I dont'n know how to describe my algorithm.
You may cover only points from convex hull. If these points are covered, all points are covered. So mininimal circle touches two or three points from convex hull.
P.S. wiki
thank you . I Agree with you.