prithivMLmods/Coder-Stat

1 2 3<h1><font color="#000">Problem B:</font> Polygonal Line Search</h1>4 5<p>6Multiple polygonal lines are given on the <i>xy</i>-plane.7Given a list of polygonal lines and a template,8you must find out polygonal lines9which have the same shape as the template.10</p>11 12<p>13A polygonal line consists of several line segments parallel to <i>x</i>-axis or14<i>y</i>-axis.  It is defined by a list of <i>xy</i>-coordinates of vertices from the start-point to the end-point in order,15and always turns 90 degrees at each vertex.16A single polygonal line does not pass the same point twice.17 18 19 20Two polygonal lines  have the same shape when they21fully overlap each other only with rotation and translation22within <i>xy</i>-plane (i.e. without magnification or a flip).23The vertices given in reverse order from the start-point to the end-point is the24same as that given in order.25</p>26 27<p>28Figure 1 shows examples of polygonal lines.29In this figure, polygonal lines A and B have the same shape.30</p>31 32 33<p>34Write a program that answers polygonal lines which have the same shape  as35the template.36</p>37 38 39 40<center>41<table>42<tr>43  <td ALIGN="center"><img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_polygonalLine"></td>44</tr>45<tr>46  <td ALIGN="center">Figure 1: Polygonal lines </td>47 48</tr>49</table>50</center>51 52 53<h2>Input</h2>54 55<p>56The input consists of multiple datasets.57The end of the input is indicated by a line which contains a zero.58</p>59 60 61<p>62A dataset is given as follows.63<blockquote>64<I>n</I><BR>65Polygonal line<SUB>0</SUB><BR>66Polygonal line<SUB>1</SUB><BR>67Polygonal line<SUB>2</SUB><BR>68...<BR>69Polygonal line<SUB><I>n</I></SUB>70</blockquote>71 72<I>n</I> is the number of polygonal lines for the object of search on73<i>xy</i>-plane.74<I>n</I> is an integer, and  1 &lt;= <I>n</I> &lt;= 50.75Polygonal line<SUB>0</SUB> indicates the template.76</p>77<p>78A polygonal line is given as follows. 79</p>80 81 82 83 84<blockquote>85<I>m</I><BR>86<I>x<SUB>1</SUB></I> <I>y<SUB>1</SUB></I><BR>87<I>x<SUB>2</SUB></I> <I>y<SUB>2</SUB></I><BR>88...<BR>89<I>x<SUB>m</SUB></I> <I>y<SUB>m</SUB></I><BR>90</blockquote>91 92</p>93 94<p>95<I>m</I> is the number of the vertices of a polygonal line (3 &lt;= <I>m</I> &lt;= 10).96 97<I>x<SUB>i</SUB></I> and <I>y<SUB>i</SUB></I>, separated by a space,98are the <i>x</i>- and <i>y</i>-coordinates99 of a vertex, respectively (-10000 &lt; <I>x<SUB>i</SUB></I> &lt; 10000, -10000 &lt;<I>y<SUB>i</SUB></I> &lt; 10000). 100</p>101 102 103<h2>Output</h2>104 105<p> 106For each dataset in the input, your program should report numbers assigned to the polygonal lines that have the same shape as the template, in ascending order.107Each number must be written in a separate line without any other characters such as leading or trailing spaces. 108</p>109 110<p> 111Five continuous "+"s must be placed in a line at the end of each dataset.112</p>113 114 115<h2>Sample Input</h2>116<pre>117511851190 01202 01212 11224 11234 012451250 01260 2127-1 2128-1 41290 413051310 01320 1133-2 1134-2 21350 213651370 01380 -11392 -11402 01414 014251430 01442 01452 -11464 -11474 014851490 01502 01512 11524 11534 015441554156-60 -75157-60 -78158-42 -78159-42 -6160416110 316210 7163-4 7164-4 401654166-74 66167-74 63168-92 63169-92 1351704171-12 22172-12 25173-30 25174-30 -47175417612 -2217712 -2517830 -2517930 4718031815182-8 5183-8 21840 21850 41868 41875188-3 -11890 -11900 7191-2 7192-2 161935194-1 6195-1 31967 31977 519816 519952000 12010 -22028 -22038 020417 02050206</pre>207 208<h2>Output for the Sample Input</h2>209<pre>210121132125213+++++21432154216+++++217+++++218</pre>219 220 221 222