| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 6 | adamant | 157 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
Given a convex polygon P, find the largest-area inscribed triangle is a very classical problem.
It's well known that it can be solved by rotating calipers in O(n) complexity.
But this paper said, the technique rotating calipers was found to be incorrect.
So confused.
Live a healthy life , stay away from Geometry
You can check for yourself.
I implemented the algorithm from the original paper and it seems like the provided breaking case is valid and breaks it (code, case).
Can you re-post these? It now returns 404, document not found
Is there an O(n^2) algorithm that is easy to implement instead of O(n)? Any code or links would be appreciated.
I even remember coding this problem at the Petrozavodsk camp...
Model solution must have also been wrong lol
Do you have a link to the problem?
Rotating calipers as such is not incorrect. This is the name for a general algorithm design technique (see https://en.wikipedia.org/wiki/Rotating_calipers ) and most algorithms based on the technique are correct.
The thing that is incorrect is one particular application of the technique: Dobkin and Snyder's algorithm for the largest inscribed triangle. The counterexample you linked works, the algorithm isn't correct.
The 1992 paper by Chandran and Mount gives a correct[*] O(n) algorithm for that problem. Their algorithm is also based on the rotating calipers technique, but the details are different.
[*] up to my best knowledge
As is known to all, rotating calipers has 16 ways of pronunciation in Chinese (because it is written in 4 Chinese characters, each having 2 ways pronunciation).
It looks Your text to link here... is a such problem. The tests are generated with some kind of random, so I think the standard solutions may based on some randomization, and I have tried so many rotating calipers solutions and all of them got Wrong Answer(see my wa 31 times!). However, my submission 224617648 base on rotating calipers passed all datas. So can someone try to hack this and tell me how to use randomization to solve this problem?