P4496 [CTSC2009] Immigration Station Site Selection

In the year 2323, with technological advances and the increasingly severe population pressure on Earth, humanity began large-scale migration to Mars. Encouragingly, the first step of the migration project achieved great success, and $N$ immigration stations have already been established on the surface of Mars, where the $i$-th station is at coordinates $(u_i, v_i)$. However, when proceeding with subsequent migration work, people encountered a serious problem: how to choose the locations for the new immigration stations. After investigation, it has been determined that $M$ new immigration stations need to be built on Mars. It is known that the information transmission flow between the original $i$-th station and the new $j$-th station is $A_{i,j}$, and the information transmission flow between the new $j$-th station and the $k$-th new station is $B_{j,k}$. At the same time, assume that the cost to transmit one unit of flow over one unit of distance is $1$, where the distance is defined as the Manhattan distance. The Manhattan distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is defined as follows: $$ \mathrm{ManhattanDist}( (x_1, y_1), (x_2, y_2) ) = |x_1 - x_2| + |y_1 - y_2| $$ Now the problem is: given the addresses of the $N$ existing immigration stations and the information flow matrices $A$ and $B$, you need to choose locations for these $M$ new immigration stations so that the total information transmission cost is minimized.

The input files are *locate1.in~locate10.in*. The first line contains two integers $N$, $M$, representing the number of existing immigration stations and the number of new stations to be built. The next $N$ lines each contain two integers, representing the coordinates of the existing stations. The next $N$ lines each contain $M$ integers, representing the information flow matrix $A$. In the final $M-1$ lines, the $i$-th line contains $M-i$ integers, where the $j$-th of them represents $B_{i,i+j}$.

The output files are *locate1.out~locate10.out*, where *locate?.out* corresponds to the answer for *locate?.in*. The first line of the output is an integer, representing the total information transmission cost you computed. The next $M$ lines each contain two integers; the $i$-th line represents the coordinates of the $i$-th newly built immigration station.

The input testdata for this problem can be downloaded from: [Baidu Netdisk](https://pan.baidu.com/s/1hEbcB45kL25wbXqEeew7Yg). 【Scoring Criteria】 Each test point is scored independently. For each test point, if your output file is invalid (e.g., file format error, output not meeting requirements, etc.), you receive 0 points for that test point. Otherwise, let your answer be $ans$. For different test points, we also set 10 scoring-related constants satisfying $c_1 \le c_2 \le c_3 \le c_4 \le c_5 \le c_6 \le c_7 \le c_8 \le c_9 \le c_{10}$. Your score for that test point is determined by the following statements: - If $ans > c_{10}$, you get 0 points. - If $ans \le c_{10}$, you get 1 point. - If $ans \le c_9$, you get 2 points. - If $ans \le c_8$, you get 3 points. - If $ans \le c_7$, you get 4 points. - If $ans \le c_6$, you get 5 points. - If $ans \le c_5$, you get 6 points. - If $ans \le c_4$, you get 7 points. - If $ans \le c_3$, you get 8 points. - If $ans \le c_2$, you get 9 points. - If $ans \le c_1$, you get 10 points. - ~~If $ans < c_1$, you get 12 points.~~ - If multiple conditions are satisfied, the highest applicable score is taken as the final score. 【Special Reminder】 Please properly save the input files *locate\*.in* and your outputs *locate\*.out*, and back them up in time to avoid accidental deletion. ☺ Translated by ChatGPT 5