AT_ahc057_a [AHC057A] Molecules

AtCoder Laboratory is engaged in the development of new molecules. Takahashi, a genius chemist, can freely bond atoms that move around at any timing he chooses to form molecules. However, bonding atoms consumes energy depending on the distance between them, so he wants to create the required number of molecules using as little energy as possible.

Consider a two-dimensional plane defined by $ 0 \leq x < L = 10^5 $ and $ 0 \leq y < L = 10^5 $ . This plane has a [toroidal](https://en.wikipedia.org/wiki/Torus) structure, meaning the left and right edges ( $ x = 0 $ and $ x = L $ ), as well as the top and bottom edges ( $ y = 0 $ and $ y = L $ ), are connected. Any coordinates outside this range are normalized to fall within $ 0 \leq x, y < L $ by taking the remainder when divided by $ L $ for both $ x $ and $ y $ . For example, the position reached by moving $ (-20000, 30000) $ from $ (10000, 90000) $ is $ (90000, 20000) $ . There are $ N $ points on this plane. At time $ t = 0 $ , the initial position $ (x_i, y_i) $ ( $ 0 \leq x_i, y_i < L $ ) and initial velocity $ (vx_i, vy_i) $ ( $ -100 \leq vx_i, vy_i \leq 100 $ ) of the $ i $ -th point ( $ 0 \leq i < N $ ) are given as input. In the initial state, each point forms an independent connected component. At each time $ t = 0, 1, \ldots, T - 1 $ , the following two phases are processed in order: **1. Bonding Phase** and **2. Movement Phase**. **1. Bonding Phase** At time $ t $ , it is possible to **bond** two points that belong to different connected components. Multiple bonds may be performed in the same time step. Let $ (x_i, y_i) $ be the position of point $ i $ at time $ t $ , and $ (x_j, y_j) $ be the position of point $ j $ at time $ t $ . The **bonding cost** $ D $ for bonding point $ i $ and point $ j $ is calculated using the following distance formula: \\\[ D = \\mathrm{round}\\left( \\sqrt{ \\bigl(\\min(L - \\Delta x,\\ \\Delta x)\\bigr)^2 + \\bigl(\\min(L - \\Delta y,\\ \\Delta y)\\bigr)^2 } \\right) \\\] \\\[ \\Delta x = |x\_i - x\_j|,\\quad \\Delta y = |y\_i - y\_j| \\\] When two points are bonded, the velocity of the resulting connected component is updated according to the law of conservation of momentum. Suppose that before the bond, point $ i $ belongs to connected component $ A $ moving at velocity $ (vx_A, vy_A) $ , and point $ j $ belongs to connected component $ B $ moving at velocity $ (vx_B, vy_B) $ . Then, for all points belonging to connected components $ A $ and $ B $ , the velocity $ (vx_{\text{new}}, vy_{\text{new}}) $ after bonding is updated as follows: \\\[ (vx\_{\\text{new}}, vy\_{\\text{new}}) = \\left( \\frac{|A| \\times vx\_A + |B| \\times vx\_B}{|A| + |B|}, \\frac{|A| \\times vy\_A + |B| \\times vy\_B}{|A| + |B|} \\right) \\\] Here, $ |A| $ and $ |B| $ denote the number of points in connected components $ A $ and $ B $ , respectively. After bonding, all points in the resulting connected component will move with **the same velocity**. The positions of the points do not change due to bonding. Additionally, the order in which bonds are performed within the same time step does not affect the resulting positions, bonding costs, or velocities of the connected components. Coordinates and velocities may become fractional, but all computations are performed using double-precision floating-point arithmetic. **2. Movement Phase** The positions of all points in each connected component are updated simultaneously. Let $ (x_i, y_i) $ be the position of point $ i $ at time $ t $ , and let $ (vx_i, vy_i) $ be the velocity of the connected component to which point $ i $ belongs. Then, the position $ (x_i', y_i') $ of point $ i $ at time $ t + 1 $ is updated as follows: \\\[ (x\_i', y\_i') = ((x\_i + vx\_i) \\bmod L, (y\_i + vy\_i) \\bmod L) \\\] Plan the bonds so that at time $ T $ , the number of connected components is **exactly $ M $** , and the size of each connected component is **exactly $ K $** , while minimizing the **total bonding cost $ D $** . #### Example of Bonding and Movement >  > > The figure above illustrates an example of bonding three points into a single connected component. First, the two points at the lower left and lower right are bonded, and their direction of movement changes upward. Next, they are bonded with the point moving to the right at the top, and the direction of movement changes to upward-right.

Input is given from Standard Input in the following format: > $ N $ $ T $ $ M $ $ K $ $ L $ $ x_0 $ $ y_0 $ $ vx_0 $ $ vy_0 $ $ x_1 $ $ y_1 $ $ vx_1 $ $ vy_1 $ $ \vdots $ $ x_{N-1} $ $ y_{N-1} $ $ vx_{N-1} $ $ vy_{N-1} $ - The total number of points is $ N = 300 $ . - The total number of steps is $ T = 1000 $ . - The target number of connected components is $ M = 10 $ . - The target size of each connected component is $ K = 30 $ . - The side length of the space is $ L = 10^5 $ . - $ (x_i, y_i) $ represents the initial position of point $ i $ , where $ 0 \leq x_i, y_i < L $ and values are integers. - $ (vx_i, vy_i) $ represents the initial velocity of point $ i $ , where $ -100 \leq vx_i, vy_i \leq 100 $ and values are integers.

Output exactly $ N - M $ lines to Standard Output. Each line consists of the following three integers, representing that point $ i $ and point $ j $ are bonded at time $ t $ . The order of the output is arbitrary, but the processing is performed in ascending order of time $ t $ . > $ t $ $ i $ $ j $ The output must satisfy the following conditions: - $ 0 \leq t < T $ - $ 0 \leq i, j < N $ , and $ i \neq j $ [Show example](https://img.atcoder.jp/ahc057/BJTm8xSg.html?lang=en&seed=0&output=sample)

### Scoring Let the total bonding cost of all bonds be $ D_{\text{sum}} $ . The score for a single test case is calculated as follows. A higher score is better. \\\[ \\mathrm{Score} = \\mathrm{round}\\!\\left(10^{6} \\times \\log\_{2}\\!\\left( \\frac{L \\times (N - M)}{D\_{\\text{sum}} + 1} \\right)\\right) \\\] The result will be WA in the following cases: - If the output is invalid - If at time $ T $ , the number of connected components is not **exactly $ M $** , or the size of each connected component is not **exactly $ K $** - If a bond is specified between two points that already belong to the same connected component There are $ 150 $ test cases, and the score of a submission is the total score for each test case. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE , and the score of the submission will be zero. The highest score obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time. ### Input Generation $ \mathrm{rand}(L,U) $ : Randomly generates an integer between $ L $ and $ U $ , inclusive, with uniform probability. **Generating Initial Positions** For each point $ i $ , independently generate $ x_i = \mathrm{rand}(0, L - 1) $ and $ y_i = \mathrm{rand}(0, L - 1) $ . **Generating Initial Velocities** For each point $ i $ , independently generate $ vx_i = \mathrm{rand}(-100, 100) $ and $ vy_i = \mathrm{rand}(-100, 100) $ . ### Tools (Input generator and visualizer) - [Web version](https://img.atcoder.jp/ahc057/BJTm8xSg.html?lang=en): This is more powerful than the local version providing animations. - [Local version](https://img.atcoder.jp/ahc057/BJTm8xSg.zip): You need a compilation environment of [Rust language](https://www.rust-lang.org/). - [Pre-compiled binary for Windows](https://img.atcoder.jp/ahc057/BJTm8xSg_windows.zip): If you are not familiar with the Rust language environment, please use this instead. Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.