Are there beautifull solution? The one other from bruteforce

Yes, there are exists one very beautiful O(N^2) solution. But the practical complexity of this algo is much less :)

There is also almost O(N) solution, but that's due to weak tests (probably there is a proof that N*log(N)) is enough. Just go forward and swap vertices if they form non-acute angle (that's WA14). Then go backward and do the same (that's WA22). Then do that in a loop 10 times back and forth, and get weak AC :)

P.S: Even 2 such passes is enough (no proof, just such tests). And I think there is a proof that N passes is always enough.

Edited by author 07.08.2022 12:28

Edited by author 07.08.2022 12:30