思维1846D · Rudolph and Christmas Tree
Rudolph 画了一棵美丽的圣诞树，并决定把这张画打印出来。然而，墨盒里的墨水常常在最不方便的时候用完。因此，Rudolph 想提前计算他需要多少绿色墨水。
这棵树是一根竖直的树干，在不同高度上长着相同的三角形树枝。树干的粗细可以忽略不计。
每根树枝都是一个底为 d、高为 h 的等腰三角形，其底边垂直于树干。这些三角形向上倾斜排列，树干恰好从正中间穿过。第 i 个三角形的底边位于高度 y_i 处。
下图展示了一棵 d = 4、h = 2 且三根树枝的底边分别位于高度 [1, 4, 5] 的树的例子。
帮助 Rudolph 计算树枝的总面积。
输入 / 输出 / 样例（含数据范围）· 不写代码可以跳过
输入
第一行包含一个整数 t（1 ≤ t ≤ 10^4）——测试数据的数量。
接下来是各测试数据的描述。
每个测试数据的第一行包含三个整数 n, d, h（1 ≤ n, d, h ≤ 2 · 10^5）——分别是树枝数量、底边长度和树枝高度。
每个测试数据的第二行包含 n 个整数 y_i（1 ≤ y_i ≤ 10^9，y_1 < y_2 < ... < y_n）——树枝底边的高度。
所有测试数据中 n 的总和不超过 2 · 10^5。
输出
对于每个测试数据，在单独一行输出一个实数——树枝的总面积。如果答案的绝对误差或相对误差不超过 10^{-6}，则视为正确。
样例
输入
5
3 4 2
1 4 5
1 5 1
3
4 6 6
1 2 3 4
2 1 200000
1 200000
2 4 3
9 11
输出
11
2.5
34.5
199999.9999975
11.333333
提示
难度 1200 · constructive algorithms, geometry, math
构造1081B · Farewell Party
Chouti 和他的同学们很快就要上大学了。为了彼此告别，班级策划了一场盛大的告别派对，同学、老师和家长们在派对上唱歌跳舞。
Chouti 记得有 n 个人参加了那场派对。为了让派对更有趣，每个人都戴了一顶帽子，帽子共有 n 种奇怪的样式，编号为 1, 2, … n。可能有好几个人戴着同样样式的帽子。有些样式的帽子可能没有人戴。
派对结束后，第 i 个人说，有 a_i 个人戴的帽子与他自己的不同。
已经过去好几天了，所以 Chouti 把别人的帽子都忘了，但他对此很好奇。设 b_i 为第 i 个人所戴帽子的样式编号，Chouti 想让你找出任意一组可能的 b_1, b_2, …, b_n，使其不与任何人的说法矛盾。因为有些人可能记性不好，所以可能根本无解。
输入 / 输出 / 样例（含数据范围）· 不写代码可以跳过
输入
第一行包含一个整数 n（1 ≤ n ≤ 10^5），表示派对中的人数。
第二行包含 n 个整数 a_1, a_2, …, a_n（0 ≤ a_i ≤ n-1），表示人们的说法。
输出
如果无解，输出一行 "Impossible"。
否则，输出 "Possible"，然后输出 n 个整数 b_1, b_2, …, b_n（1 ≤ b_i ≤ n）。
如果有多个答案，输出其中任意一个。
样例
输入
3
0 0 0
输出
Possible
1 1 1
输入
5
3 3 2 2 2
输出
Possible
1 1 2 2 2
输入
4
0 1 2 3
输出
Impossible
提示
在第一个样例的答案中，所有帽子都相同，所以每个人都会说，没有人戴的帽子与样式 1 不同。
在第二个样例的答案中，第一个人和第二个人戴的是样式 1 的帽子，其他所有人都戴样式 2 的帽子。
所以前两个人会说，有三个人戴的帽子与他们自己的不同。同样地，最后三个人会说，有两个人戴的帽子与他们自己的不同。
在第三个样例中，可以证明不存在解。
在第一个和第二个样例中，其他可能的配置也是可能的。
提示
难度 1500 · constructive algorithms, implementation