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)$。这个无论如何不会出问题。


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

代码

Submission #111865943 - Codeforces
Codeforces. Programming competitions and contests, programming community