prithivMLmods/Coder-Stat

1 2<script type="text/x-mathjax-config">3  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], skipTags: ["script","noscript","style","textarea","code"], processEscapes: true }});4</script>5<script type="text/javascript" async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS_HTML"></script>6 7<h2>Problem B8  Parallel Lines9</h2>10 11<p>12  Given an even number of distinct planar points, consider coupling all of the points into pairs. All the possible couplings are to be considered as long as all the given points are coupled to one and only one other point.13</p>14 15<p>16  When lines are drawn connecting the two points of all the coupled point pairs, some of the drawn lines can be parallel to some others. Your task is to find the maximum number of parallel line pairs considering all the possible couplings of the points.17</p>18 19<p>20  For the case given in the first sample input with four points, there are three patterns of point couplings as shown in Figure B.1. The numbers of parallel line pairs are 0, 0, and 1, from the left. So the maximum is 1.21</p>22 23<center>24<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_ICPCAsia2017_parallelLines1">25<p>Figure B.1. All three possible couplings for Sample Input 1</p>26</center>27 28<p>29  For the case given in the second sample input with eight points, the points can be coupled as shown in Figure B.2. With such a point pairing, all four lines are parallel to one another. In other words, the six line pairs $(L_1, L_2)$, $(L_1, L_3)$, $(L_1, L_4)$, $(L_2, L_3)$, $(L_2, L_4)$ and $(L_3, L_4)$ are parallel. So the maximum number of parallel line pairs, in this case, is 6.30</p>31 32 33<h3>Input</h3>34<p>35  The input consists of a single test case of the following format.36</p>37 38<pre>39$m$40$x_1$ $y_1$41...42$x_m$ $y_m$43</pre>44 45<center>46<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_ICPCAsia2017_parallelLines2">47<p>  Figure B.2. Maximizing the number of parallel line pairs for Sample Input 2</p>48</center>49 50<p>51  The first line contains an even integer $m$, which is the number of points ($2 \leq m \leq 16$). Each of the following $m$ lines gives the coordinates of a point. Integers $x_i$ and $y_i$ ($-1000 \leq x_i \leq 1000, -1000 \leq y_i \leq 1000$) in the $i$-th line of them give the $x$- and $y$-coordinates, respectively, of the $i$-th point.52</p>53 54<p>55  The positions of points are all different, that is, $x_i \ne x_j$ or $y_i \ne y_j$ holds for all $i  \ne j$. Furthermore, No three points lie on a single line.56</p>57 58 59<h3>Output</h3>60 61<p>62  Output the maximum possible number of parallel line pairs stated above, in one line.63</p>64 65<h3>Sample Input 1</h3>66<pre>674680 0691 1700 2712 472</pre>73 74<h3>Sample Output 1</h3>75<pre>76177</pre>78 79<h3>Sample Input 2</h3>80<pre>818820 0830 5842 2852 7863 -2875 0884 -2898 290</pre>91 92<h3>Sample Output 2</h3>93<pre>94695</pre>96 97<h3>Sample Input 3</h3>98<pre>9961000 01010 51023 -21033 51045 01055 7106</pre>107 108<h3>Sample Output 3</h3>109<pre>1103111</pre>112 113<h3>Sample Input 4</h3>114<pre>1152116-1000 10001171000 -1000118</pre>119<h3>Sample Output 4</h3>120<pre>1210122</pre>123 124<h3>Sample Input 5</h3>125<pre>12616127327 449128-509 761129-553 515130360 948131147 877132-694 468133241 320134463 -753135-206 -991136473 -738137-156 -916138-215 54139-112 -476140-452 780141-18 -335142-146 77143</pre>144 145<h3>Sample Output 5</h3>146<pre>14712148</pre>