Re: Are there beautifull solution?

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

Re: Are there beautifull solution?

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*