Mid-Central USA Programming Contest 2016


2016-11-05 09:30 AKDT

Mid-Central USA Programming Contest 2016


2016-11-05 14:30 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -1419 days 20:53:00

Time elapsed


Time remaining


Problem J
Windy Path

\includegraphics[width=0.4 \textwidth ]{windy}

Consider following along the path in the figure above, starting from $(4,4)$ and moving to $(2,5)$. Then the path turns rightward toward $(1,6)$, then sharp left to $(5,0)$ and finally sharp left again to $(4,2)$. If we use ‘L’ for left and ‘R’ for right, we see that the sequence of turn directions is given by ‘RLL’. Notice that the path does not cross itself: the only intersections of segments are the connection points along the path.

Consider the reverse problem: Given points in an arbitrary order, say $(2,5),(1,6),(4,4),(5,0),(4,2)$, could you find an ordering of the points so the turn directions along the path are given by ‘RLL’? Of course to follow the path in the figure, you would start with the third point in the list $(4,4)$, then the first $(2,5)$, second $(1,6)$, fourth $(5,0)$, and fifth $(4,2)$, so the permutation of the points relative to the given initial order would be: $3$ $1$ $2$ $4$ $5$.


The first line of the input contains an integer $N$, specifying the number of points such that $3 \leq N \leq 50$. The following $N$ lines each describe a point using two integers $x_ i$ and $y_ i$ such that $0 \le x_ i, y_ i \le 1000$. The points are distinct and no three are collinear (i.e., on the same line). The last line contains a string of $N-2$ characters, each of which is either ‘L’ or ‘R’.


A permutation of $\{ 1, \ldots , N\} $ that corresponds to a nonintersecting path satisfying the turn conditions. The numbers are to be displayed with separating spaces. (There are always one or more possible solutions, and any one may be used.)

Sample Input 1 Sample Output 1
2 5
1 6
4 4
5 0
4 2
3 1 2 4 5

Sample Input 2 Sample Output 2
1 1
2 1
1 2
2 2
3 1 4 2