Description

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.

Input Format

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)$.

Output Format

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.

4  
1.0 2.0 
3.0 1.0 
5.0 4.0 
2.0 2.0

3 2 
3  
1 3 2

Hint

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