Codeforces Round #698 Nezzar and Nice Beatmap - Computational geometry

Solution

Let's consider three points first. three point can build a triangle. So at most 1 angle equal or more than $90^\circ$.

So we get first conclusion: If a sequence of three point is equal or more than $90^\circ$, then just need replace the centered point to any one of other two.

Now let assume there already get a sequence which is match the requirement: $(d,c,b,a)$. Now let put a new point $x$ into the sequence. And put it in as last one first. So we get $(d,c,b,a,x)$.

If $(b,a,x) < 90^\circ$, then everything is fine.

Otherwise, let move $x$ forward. Get $(d,c,b,x,a)$ now. And $(b,x,a)$ much be ok. Because $(b,a,x)\geq90^\circ$. So the current issue will only be on $(c,b,x)$.

Again, if $(c,b,x) < 90^\circ$, then everything is fine. Just leave $x$ there.

Otherwise, move $x$ forward again. Get $(d,c,x,b,a)$ now. Similarly, the issue will only be on $(d,c,x)$.

Move $x$ forward again and again. When $x$ come to second. Like $(d,x,c,b,a)$ as example. Because $(d,c,x)\geq90^\circ$. So it must be fine.

So the solution is: put new point to the last. If not match, then move it forward. There must be one step can get answer.

Code

Submission #111865943 - Codeforces

Codeforces. Programming competitions and contests, programming community

Codeforces