Folding Paper

All submissions for this problem are available.
### Read problem statements in [Bengali](http://www.codechef.com/download/translated/LTIME80/bengali/PAPER.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME80/mandarin/PAPER.pdf), [Russian](http://www.codechef.com/download/translated/LTIME80/russian/PAPER.pdf), and [Vietnamese](http://www.codechef.com/download/translated/LTIME80/vietnamese/PAPER.pdf) as well. Chef has a rectangular piece of paper. He puts it on a big board in such a way that two sides of the paper are horizontal and two are vertical, and then he performs a sequence of $N$ operations. You are given a string $S$ with length $N$; for each valid $i$, the $i$th character of $S$ determines the type of the $i$th operation:  'R': Pick up the paper from the right side and fold it onto the left side.  'L': Pick up the paper from the left side and fold it onto the right side.  'U': Pick up the paper from the upper side and fold it onto the bottom side.  'D': Pick up the paper from the bottom side and fold it onto the upper side. The paper is folded in such a way that there is still a flat rectangular sheet of paper lying on the table after each operation, but it consists of multiple layers of the original sheet. The lengths of the horizontal and vertical sides of the resulting sheet (after performing these $N$ operations) are $W$ and $H$ respectively. Let's build an Euclidean coordinate system on the paper, where the point $(0, 0)$ corresponds to the bottom left corner and $(W, H)$ to the upper right corner. Chef then draws $M$ points on this folded sheet of paper. The ink used to draw them soaks deep into the paper, so each point is drawn on all layers of the paper (and also on both faces of each layer). Finally, Chef completely unfolds the paper. He's asking you to compute the distance between the nearest pair of points. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains four spaceseparated integers $N$, $M$, $W$ and $H$.  The second line contains a single string $S$.  Each of the following $M$ lines contains two spaceseparated integers $X$ and $Y$ denoting the coordinates of one point. ### Output For each test case, print a single line containing one real number ― the minimum distance. Your answer will be considered correct if its absolute or relative error does not exceed $10^{6}$. ### Constraints  $1 \le T \le 50$  $2 \le M \le 1,000$  $1 \le N \le 1,000$  $3 \le W, H \le 10^9$  $1 \le X \le W1$  $1 \le Y \le H1$  the points are pairwise distinct ### Subtasks **Subtask #1 (50 points):** all characters of $S$ are 'U' **Subtask #2 (50 points):** original constraints ### Example Input ``` 2 6 2 10 10 ULRDDL 4 4 5 5 4 2 10 10 RUDL 1 1 9 9 ``` ### Example Output ``` 1.41421356237 2.00000000000 ```Author:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/PAPER 
Tags  easy, geometry, kingofnumbers, ltime80, observations, taran_1407 
Date Added:  25012020 
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, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, 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. 