prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem J:</font> Zigzag</H1>3 4<p>5Given several points on a plane, let’s try to solve a puzzle connecting them with a zigzag line.6The puzzle is to find the zigzag line that passes through all the given points with the minimum7number of turns. Moreover, when there are several zigzag lines with the minimum number of8turns, the shortest one among them should be found.9</p>10<p>11For example, consider nine points given in Figure 1.12</p>13 14<center>15<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_zigzag1">16<p>Figure 1: Given nine points</p>17</center>18 19<p>20A zigzag line is composed of several straight line segments. Here, the rule requests that each21line segment should pass through two or more given points.22</p>23<p>24A zigzag line may turn at some of the given points or anywhere else. There may be some given25points passed more than once.26</p>27 28<center>29<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_zigzag2">30<p>Figure 2: Zigzag lines with three turning points.</p>31</center>32 33<p>34Two zigzag lines with three turning points are depicted in Figure 2 (a) and (b) for the same35set of given points shown in Figure 1. The length of the zigzag line in Figure 2 (a) is shorter than that in Figure 2 (b). In fact, the length of the zigzag line in Figure 2 (a) is the shortest36so that it is the solution for the nine points given in Figure 1.37</p>38<p>39Another zigzag line with four turning points is depicted in Figure 3. Its length is shorter than40those in Figure 2, however, the number of turning points is greater than those in Figure 2,41and thus, it is not the solution.42</p>43 44<center>45<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_zigzag3">46<p>Figure 3: Zigzag line with four turning points.</p>47</center>48 49<p>50There are two zigzag lines that passes another set of given points depicted in Figure 4 (a) and51(b).52</p>53<p>54Both have the same number of turning points, and the line in (a) is longer than that in (b).55However, the solution is (a), because one of the segments of the zigzag line in (b) passes only56one given point, violating the rule.57</p>58 59<center>60<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_zigzag4">61<p>Figure 4: Zigzag line with two turning points (a), and not a zigzag line concerned (b).</p>62</center>63 64<p>65Your job is to write a program that solves this puzzle.66</p>67 68<H2>Input</H2>69 70<p>71The input consists of multiple datasets, followed by a line containing one zero. Each dataset72has the following format.73</p>74<pre>75<i>n</i>76<i>x</i><sub>1</sub> <i>y</i><sub>1</sub>77   .78   .79   .80<i>x</i><sub><i>n</i></sub> <i>y</i><sub><i>n</i></sub>81</pre>82 83<p>84Every input item in a dataset is a non-negative integer. Items in a line are separated by a single85space.86</p>87<p>88<i>n</i> is the number of the given points. <i>x</i><sub><i>k</i></sub> and <i>y</i><sub><i>k</i></sub> (<i>k</i> = 1, . . . , <i>n</i>) indicate the position of the <i>k</i>-th89point. The order of the points is meaningless. You can assume that 2 &le; <i>n</i> &le; 10, 0 &le; <i>x</i><sub><i>k</i></sub> &le; 10,90and 0 &le; <i>y</i><sub><i>k</i></sub> &le; 10.91</p>92 93<H2>Output</H2>94 95<p>96For each dataset, the minimum number of turning points and the length of the shortest zigzag97line with that number of turning points should be printed, separated by a space in a line. The98length should be in a decimal fraction with an error less than 0.0001 (= 1.0 &times; 10<sup>-4</sup> ).99</p>100<p>101You may assume that the minimum number of turning points is at most four, that is, the number102of line segments is at most five.103</p>104<p>105The example solutions for the first four datasets in the sample input are depicted in Figure 5106and 6.107</p>108 109<H2>Sample Input</H2>110<pre>11121120 011310 911441150 01163 11170 31183 3119101202 21214 21226 21232 41244 41256 41262 61274 61286 61293 3130101310 01322 01334 01340 21352 21364 21370 41382 41394 41406 814191420 01431 01443 01450 11461 11473 11480 21491 21502 2151101520 01531 01540 11551 11569 91579 1015810 915910 101600 216110 8162101630 01640 101652 01662 11672 71682 101695 11706 71719 217210 91730174</pre>175 176<H2>Output for the Sample Input</H2>177<pre>1780 13.453624051791 18.486832981803 24.142135621814 24.948136731823 12.242640691833 60.782896221843 502.7804353185</pre>186 187<center>188<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_zigzag5">189<p>Figure 5: Example solutions for the first and the second datasets in the sample inputs.</p>190</center>191<br>192<center>193<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_zigzag6">194<p>Figure 6: Example solutions for the third and the fourth datasets in the sample inputs.</p>195</center>196 197