Codeforces Round #698 Nezzar and Nice Beatmap 几何

题意

给你一串点。然后问你这一串点的某种排列能否使得其中任意连续的三点i, i+1, i+2满足由这三点构成的夹角为锐角。如果有这种排列，则输出这种排列。没有就输出-1.

题解

考量三角形。三角形最多有一个直角或锐角。那么对于任意三点，如果这三个点的排列出来的结果是钝角。那么这三个点换任意一个顺序都是锐角。

那假设前面已经排好了若干个点，$(d,c,b,a)$。现在新加一个点x进来，放在最后。假设加进来后最后三位的排列为$(b,a,x)$。

如果最后三位不出问题，那当让是极好的。但如果除了问题，我们就把x往前挪一位。于是得到最后四位：$(c,b,x,a)$。因为$(b,a,x)$是钝角，所以$(b,x,a)$一定是锐角。那么目前问题只会出在$(c,b,x)$上。

同样的，不出问题还好，假设$(c,b,x)$是钝角。那我再往前挪，得到$(d,c,x,b,a)$。同理，出问题的一定只可能是$(d,c,x)$。

如此往复，直到尽头时我们发现。（假设d就是第一个了），再往前挪，得到$(d,x,c,b,a)$。这个无论如何不会出问题。

于是，每次放最后，不行就往前挪，再不行再挪。总能挪到有解的地方。

代码