Polygon Chain

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/FEB20/hindi/POLCHAIN.pdf), [Bengali](http://www.codechef.com/download/translated/FEB20/bengali/POLCHAIN.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/FEB20/mandarin/POLCHAIN.pdf), [Russian](http://www.codechef.com/download/translated/FEB20/russian/POLCHAIN.pdf), and [Vietnamese](http://www.codechef.com/download/translated/FEB20/vietnamese/POLCHAIN.pdf) as well. A polygon $T$ is said to be *inside* a polygon $S$ if all points that lie strictly inside $T$ (not on the perimeter of $T$) also lie strictly inside $S$. A multiset of polygons $\{Q_1, Q_2, \ldots, Q_r\}$ is said to *form a chain* if there is a permutation $p_1, p_2, \ldots, p_r$ of the integers $1$ through $r$ such that for each $i$ ($1 \le i \lt r$), $Q_{p_i}$ is inside $Q_{p_{i+1}}$. You are given $N$ convex polygons $P_1, P_2, \ldots, P_N$ in a 2D Cartesian coordinate system. Every $10^{100}$ seconds, you may choose one of the polygons and translate it by upto $10^{100}$ either along the $x$axis or along the $y$axis. Find the minimum amount of time necessary to make all $N$ polygons form a chain or decide that it is impossible. ### Input  The first line of the input contains a single integer $N$. The descriptions of $N$ polygons follow.  For each polygon:  The first line contains a single integer $M$ denoting the number of its vertices.  The following $M$ lines describe the vertices in counterclockwise order. Each of these lines contains two spaceseparated integers $x$ and $y$ denoting the coordinates of one vertex. ### Output If it is impossible to make the polygons form a chain, print a single line containing the integer $1$. Otherwise, print a single line containing one real number ― the minimum amount of time. Your answer will be considered correct if its absolute or relative error does not exceed $10^{6}$. ### Constraints  $2 \le N \le 20$  the sum of $M$ over all polygons does not exceed $100$  $x, y \le 100$ ### Subtasks **Subtask #1 (10 points):** $N = 2$ and both polygons are axisaligned rectangles **Subtask #2 (20 points):** $N = 2$ **Subtask #3 (20 points):** all polygons are axisaligned rectangles **Subtask #4 (50 points):** original constraints ### Example Input ``` 2 4 1 3 2 2 3 3 2 4 4 0 0 2 0 2 2 0 2 ``` ### Example Output ``` 3 ``` ### Explanation **Example case 1:** Both $P_1$ and $P_2$ are squares. If we move $P_2$ by $1$ unit in the $x$direction and by $2$ units in the $y$direction, the vertices of $P_1$ become the midpoints of edges of $P_2$.Author:  jtnydv25 
Editorial  https://discuss.codechef.com/problems/POLCHAIN 
Tags  feb20, geometry, hard, jtnydv25, tmwilliamlin 
Date Added:  6022020 
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. 