prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem F: </font>Directional Resemblance</H1>3 4<p>5Vectors have their directions and two vectors make an angle between them. Given a set of three-dimensional vectors, your task is to find the pair among them that makes the smallest angle.6</p>7 8<H2>Input</H2>9 10<p>11The input is a sequence of datasets. A dataset specifies a set of three-dimensional vectors, some of which are directly given in the dataset and the others are generated by the procedure described below.12</p>13 14<p>15Each dataset is formatted as follows.16</p>17 18<pre>19<var>m</var> <var>n</var> <var>S</var> <var>W</var>20<var>x<sub>1</sub></var> <var>y<sub>1</sub></var> <var>z<sub>1</sub></var>21<var>x<sub>2</sub></var> <var>y<sub>2</sub></var> <var>z<sub>2</sub></var>22:23<var>x<sub>m</sub></var> <var>y<sub>m</sub></var> <var>z<sub>m</sub></var>24</pre>25 26<p>27The first line contains four integers <var>m</var>, <var>n</var>, <var>S</var>, and <var>W</var>.28</p>29 30<p>31The integer <var>m</var> is the number of vectors whose three components are directly specified in the32dataset. Starting from the second line, <var>m</var> lines have the three components of <var>m</var> vectors. The <var>i</var>-th line of which indicates the vector <var>v<sub>i</sub></var> = (<var>x<sub>i</sub></var>, <var>y<sub>i</sub></var>, <var>z<sub>i</sub></var>). All the vector components are positive integers less than or equal to 100.33</p>34 35<p>36The integer <var>n</var> is the number of vectors generated by the following procedure.37</p>38 39<pre>40int g = S;41for(int i=m+1; i<=m+n; i++) {42  x[i] = (g/7)    %100 + 1;43  y[i] = (g/700)  %100 + 1;44  z[i] = (g/70000)%100 + 1;45  if( g%2 == 0 ) { g = (g/2); }46  else           { g = (g/2) ^ W; }47}48</pre>49 50<p>51For <var>i = m + 1, . . . , m + n</var>, the <var>i</var>-th vector <var>v<sub>i</sub></var> of the set has three components <span>x[i]</span>, <span>y[i]</span>, and <span>z[i]</span> generated by this procedure.52</p>53 54<p>55Here, values of <span>S</span> and <span>W</span> are the parameters <var>S</var> and <var>W</var> given in the first line of the dataset. You may assume 1 &le; <var>S</var> &le; 10<sup>9</sup> and 1 &le; <var>W</var> &le; 10<sup>9</sup>.56</p>57 58<p>59The total number of vectors satisfies 2 &le; <var>m + n</var> &le; 12 &times; 10<sup>4</sup>. Note that exactly the same vector may be specified twice or more in a single dataset.60</p>61 62<p>63A line containing four zeros indicates the end of the input. The total of <var>m+n</var> for all the datasets in the input never exceeds 16 &times; 10<sup>5</sup>.64</p>65 66 67<H2>Output</H2>68 69<p>70For each dataset, output the pair of vectors among the specified set with the smallest non-zero angle in between. It is assured that there are at least two vectors having different directions.71</p>72 73<p>74Vectors should be indicated by their three components. The output for a pair of vectors <var>v<sub>a</sub></var> and <var>v<sub>b</sub></var> should be formatted in a line as follows.75</p>76 77<pre>78<var>x<sub>a</sub></var> <var>y<sub>a</sub></var> <var>z<sub>a</sub></var> <var>x<sub>b</sub></var> <var>y<sub>b</sub></var> <var>z<sub>b</sub></var>79</pre>80 81<p>82Two vectors (<var>x<sub>a</sub></var>, <var>y<sub>a</sub></var>, <var>z<sub>a</sub></var>) and (<var>x<sub>b</sub></var>, <var>y<sub>b</sub></var>, <var>z<sub>b</sub></var>) are ordered in the dictionary order, that is, <var>v<sub>a</sub></var> &lt; <var>v<sub>b</sub></var> if <var>x<sub>a</sub></var> &lt; <var>x<sub>b</sub></var>, or if <var>x<sub>a</sub> = x<sub>b</sub></var> and <var>y<sub>a</sub></var> &lt; <var>y<sub>b</sub></var>, or if <var>x<sub>a</sub> = x<sub>b</sub></var>, <var>y<sub>a</sub> = y<sub>b</sub></var> and <var>z<sub>a</sub></var> &lt; <var>z<sub>b</sub></var>. When a vector pair is output, the smaller vector in this order should be output first.83</p>84 85<p>86If more than one pair makes the equal smallest angle, the pair that is the smallest among them in the dictionary order between vector pairs should be output. The pair (<var>v<sub>i</sub></var>, <var>v<sub>j</sub></var>) is smaller than the pair (<var>v<sub>k</sub></var>, <var>v<sub>l</sub></var>) if <var>v<sub>i</sub></var> &lt; <var>v<sub>k</sub></var>, or if <var>v<sub>i</sub> = v<sub>k</sub></var> and <var>v<sub>j</sub></var> &lt; <var>v<sub>l</sub></var>.87</p>88 89<H2>Sample Input</H2>90<pre>914 0 2013 1124921 1 1932 2 2942 1 1951 2 1962 100 131832453 1298002319742 40 469842 40 46990 100000 7004674 4845214381000 0 0 0101</pre>102 103<H2>Output for the Sample Input</H2>104<pre>1051 1 1 1 2 110642 40 46 83 79 9110792 92 79 99 99 85108</pre>