[WC2010] 能量场

官方spj：https://www.luogu.org/paste/03wjc4ne spj provider: @hehezhou

物理学家栋栋最近在研究一个能量场。在这个能量场中有n个粒子，每个粒子都有两个属性：质量m和结合系数c。 栋栋发现，在这个能量场中，每个粒子都有两极，N极和S极。两个粒子相遇时，符合“同极相斥，异极相吸”的原则，只能是一个粒子的N极和另一个粒子的S极连接到一起。当质量为ma，结合系数为ca的粒子a的N极与另一个质量为mb，结合系数为cb的粒子b的S极直接连接时，可以产生大小为 $m_a m_b (c_a - c_b)$ 的结合能量。 请解决以下两个问题： 1. 在能量场的n个粒子中哪两个粒子直接连接的能量最大。 2. 栋栋发明了一种方法，能选择其中的任意k个粒子p1, p2, …, pk，将pi的 N极与pi+1的S极连接(1 ≤ i < k)， pk的N极与p1的S极连接， 其中p1, p2, …, pk两两不同。k可以在1至n中任意取值，如使用栋栋的这种方法连接，选择哪些粒子可以得到最大的能量。

第一行包含一个整数n，表示粒子的个数。 接下来n行，每行两个实数，第i+1行的两个实数表示第i个粒子的质量mi和结合系数ci。(0< mi, ci <10^5)

第一行包含两个整数a, b，表示将粒子a的N极与粒子b的S极连接可以得到最大的能量。 第二行包含一个整数k，表示第二问中要得到最大的能量需要多少个粒子。 第三行包含k个整数，表示p1, p2, …, pk，即第二问中的最优方案。

4  
1.0 2.0 
3.0 1.0 
5.0 4.0 
2.0 2.0

3 2 
3  
1 3 2

【样例说明】 对于第一问，第三个粒子的N极与第二个粒子的S极连接，能得到的能量为$5\times3\times(4-1) = 45$。 对于第二问，顺次连接1, 3, 2号粒子，能量为 $1\times5\times(2-4) + 5\times3\times(4-1) + 3\times1\times(1-2) = 32$。 【数据规模】 10%的数据，n ≤ 8； 20%的数据，n ≤ 15； 40%的数据，n ≤ 1 000； 50%的数据，n ≤ 5 000； 100%的数据，n ≤ 50 000。 【评分标准】 此题可能有多解，如果用你的解产生的能量与参考答案的绝对误差或相对误差小于10–5，则得满分。否则不得分。 对于本题，每问的分数各占50%。如果你的输出任何一问的格式或结果不正确，则不得分；否则如果其中的一问正确，则得到该测试点50%的分数；如果两问都正确，得到该测试点100%的分数。