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.