P4293 [WC2010] 能量场

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

物理学家栋栋最近在研究一个能量场。在这个能量场中有 $n$ 个粒子，每个粒子都有两个属性：质量 $m$ 和结合系数 $c$。 栋栋发现，在这个能量场中，每个粒子都有两极，N 极和 S 极。两个粒子相遇时，符合“同极相斥，异极相吸”的原则，只能是一个粒子的 N 极和另一个粒子的 S 极连接到一起。当质量为 $m_a$，结合系数为 $c_a$ 的粒子 $a$ 的 N 极与另一个质量为 $m_b$，结合系数为 $c_b$ 的粒子 $b$ 的 S 极直接连接时，可以产生大小为 $m_am_b(c_a-c_b)$ 的结合能量。 请解决以下两个问题： 1. 在能量场的 $n$ 个粒子中哪两个粒子直接连接的能量最大。 2. 栋栋发明了一种方法，能选择其中的任意 $k$ 个粒子 $p_1,p_2,\dots,p_k$，将 $p_i$的 N 极与 $p_i+1$ 的 S 极连接 $(1\le i

第一行包含一个整数 $n$ ，表示粒子的个数。 接下来 $n$ 行，每行两个实数，第 $i+1$ 行的两个实数表示第 $i$ 个粒子的质量 $m_i$ 和结合系数 $c_i$。$(0

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

【样例说明】 对于第一问，第三个粒子的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\le 8$； $20\%$ 的数据，$n\le 15$； $40\%$ 的数据，$n\le 1000$； $50\%$ 的数据，$n\le 5000$； $100\%$ 的数据，$n\le 50000$。 【评分标准】 此题可能有多解，如果用你的解产生的能量与参考答案的绝对误差或相对误差小于 $10^{–5}$，则得满分。否则不得分。 对于本题，每问的分数各占 $50\%$。如果你的输出任何一问的格式或结果不正确，则不得分；否则如果其中的一问正确，则得到该测试点 $50\%$ 的分数；如果两问都正确，得到该测试点 $100\%$ 的分数。