题目描述

平面上有 $N$ 个点 $P_1,P_2,\dots,P_N$，点 $P_i$ 的坐标为 $(X_i,Y_i)$。

给定正整数 $p,q$。设 $Q_{i,j}$ 为把线段 $P_iP_j$ 按 $p:q$ 内分得到的点。特别地，若 $P_i=P_j$，则 $Q_{i,j}=P_i$。

请求出所有满足 $1 \leq i \lt j \leq N$ 的正整数对 $(i,j)$ 对应的 $Q_{i,j}$ 的凸包面积。

输入格式

输入按以下格式从标准输入读入：

• $N$ $p$ $q$
• $X_1$ $Y_1$
• $X_2$ $Y_2$
• $\vdots$
• $X_N$ $Y_N$

输出格式

可以证明，在本题的约束下，所求凸包的面积一定是有理数。把该面积表示为最简分数 $\dfrac{x}{y}\ (x \geq 0, y \geq 1)$ 时，请在一行内按顺序输出 $x$ 与 $y$，中间用一个空格隔开。

4 1 2
-2 4
1 1
-3 -2
4 0

59 6

有 $Q_{1,2}=\left(-1,3\right),Q_{1,3}=\left(-\frac{7}{3},2\right),Q_{1,4}=\left(0,\frac{8}{3}\right),Q_{2,3}=\left(-\frac{1}{3},0\right),Q_{2,4}=\left(2,\frac{2}{3}\right),Q_{3,4}=\left(-\frac{2}{3},-\frac{4}{3}\right)$。

它们的凸包是按 $Q_{1,2},Q_{1,3},Q_{3,4},Q_{2,4},Q_{1,4}$ 的顺序连接而成的五边形，其面积为 $\frac{59}{6}$。

3 3 4
11 -7
2 8
-4 18

0 1

凸包的面积可能为 $0$。

10 5 7
-3677189 -8603516
3324282 8371380
-4445534 -865546
-1235744 -6761030
2732080 -9194939
8510740 4384715
-7326815 2451526
-2079912 1054509
2072791 -8408897
-4437202 -5184973

6746232144385823 48

数据范围

• $2 \leq N \leq 10^5$

• $1 \leq p \lt q \leq 10$

• $|X_i|\leq 10^7$

• $|Y_i|\leq 10^7$

• 所有输入值均为整数。

• 来源：AtCoder ABC 478 G

子任务设置

• 子任务 1（30 分）：$N \le 300$。
• 子任务 2（30 分）：$N \le 2000$。
• 子任务 3（40 分）：无特殊限制。