Polygon and String

All submissions for this problem are available.
You are given a list of $n$ points $p_0, p_1, ..., p_{n1}$ in convex position (ie. all of the points are vertices of their convex hull), such that no three points are collinear and no two points have the same $x$ or $y$ coordinate, so for any $i,j$ we have $x_i \not = x_j$ and $y_i \not = y_j$ where $p_i = (x_i, y_i)$ and $p_j= (x_j, y_j)$. You will be given a number of queries. Each query is a string $S = s_0 s_1 \ldots s_{n2}$ of length $n1$ composed of only the letters $U$ and $D$. For each string, your task is to find a permutation of the points, $p_{\sigma(0)}, p_{\sigma(1)}, ..., p_{\sigma(n1)}$, such that for $i = 0, 1, ..., n2 $ we have:  If the $s_i$ is a $U$ then y coordinate of $p_{\sigma(i)}$ is less than the y coordinate of $p_{\sigma(i+1)}$  If the $s_i$ is a $D$ then y coordinate of $p_{\sigma(i)}$ is larger than the y coordinate of $p_{\sigma(i+1)}$ Furthermore, we require that the line segments $\overline{p_{\sigma(i)} p_{\sigma(i+1)}}$ for $i = 0, 1, ..., n2$ intersect with each other only at their end points (if at all). It is guaranteed that such a permutation exists. If there are multiple solutions, you can output any one. Note: The vertices in the input are not guaranteed to be in any particular order. ### Input  The first line of the input consists of two integers $n$ and $m$, the number of points and the number of queries respectively.  The next $n$ lines contain pairs of space separated integers, corresponding to the $x$ and $y$ coordinate of the point.  The next $m$ lines contain the queries, which are strings of length $n1$. ### Output For each query, print out on a new line the permutation $\sigma(0), \sigma(1), ..., \sigma(n1)$ as a list of space separated integers. ###Constraints  $3 \le n \le 5000$  $1 \le n \cdot m \le 10000$  $0 \le x, y \le 10^7$ ### Example Input ``` 3 2 2 2 3 4 1 1 UU UD ``` ### Example Output ``` 2 0 1 2 1 0 ``` ###Explanation **Testcase 1:** The outputted permutation corresponds to this: ![Initial](https://codechef_shared.s3.amazonaws.com/download/Images/TST18GWR/POLYST... =375x375) **Testcase 2:** The outputted permutation corresponds to this: ![Initial](https://codechef_shared.s3.amazonaws.com/download/Images/TST18GWR/POLYST... =375x375)Author:  admin2 
Tags  admin2 
Date Added:  15122018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 