P4293 [WC2010] Energy Field

Official SPJ: https://www.luogu.org/paste/03wjc4ne. SPJ provider: @hehezhou.

Physicist Dongdong is studying an energy field. In this field, there are n particles, and each particle has two attributes: mass m and bonding coefficient c. Dongdong discovers that each particle has two poles, an N pole and an S pole. When two particles meet, they follow the rule “like poles repel, unlike poles attract,” and only the N pole of one particle can connect to the S pole of another. When the N pole of particle a with mass $m_a$ and coefficient $c_a$ directly connects to the S pole of particle b with mass $m_b$ and coefficient $c_b$, the produced binding energy is $m_a m_b (c_a - c_b)$. Please solve the following two problems: 1. Among the n particles, determine which ordered pair of particles, when directly connected (N of a to S of b), yields the maximum energy. 2. Dongdong invents a method that selects any k particles $p1, p2, \dots, pk$, connects the N pole of $p_i$ to the S pole of $p_{i+1}$ for $1 \le i < k$, and connects the N pole of $p_k$ to the S pole of $p1$, where $p1, p2, \dots, pk$ are pairwise distinct. The value of k can be any integer from 1 to n. Using this method, choose the particles to obtain the maximum total energy.

The first line contains an integer n, the number of particles. The next n lines each contain two real numbers. In line $i+1$, the two real numbers denote the mass $m_i$ and bonding coefficient $c_i$ of particle i. $(0 < m_i, c_i < 10^5)$.

The first line contains two integers a and b, indicating that connecting the N pole of particle a to the S pole of particle b yields the maximum energy. The second line contains an integer k, the number of particles needed to achieve the maximum total energy in problem 2. The third line contains k integers, denoting $p1, p2, \dots, pk$, i.e., the optimal sequence in problem 2.

Sample Explanation: - For the first problem, connecting the N pole of the third particle to the S pole of the second particle yields energy $5\times3\times(4-1) = 45$. - For the second problem, connecting particles 1, 3, 2 in order yields energy $1\times5\times(2-4) + 5\times3\times(4-1) + 3\times1\times(1-2) = 32$. Constraints: - For 10% of the testdata, $n \le 8$. - For 20% of the testdata, $n \le 15$. - For 40% of the testdata, $n \le 1000$. - For 50% of the testdata, $n \le 5000$. - For 100% of the testdata, $n \le 50000$. Scoring: - This problem may have multiple correct outputs. If the absolute error or relative error of your energy compared to the reference answer is less than $10^{-5}$, you receive full score; otherwise, you receive zero. - Each of the two problems is worth 50%. If the format or result of any one problem is incorrect, you receive zero; otherwise, if only one problem is correct, you receive 50% of the points for that test point; if both are correct, you receive 100% of the points for that test point. Translated by ChatGPT 5