/ 
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 625 点
問題文
座標平面上に N 個の点 P_1,P_2,\dots,P_N があります。点 P_i の座標は (X_i,Y_i) です。
正整数 p,q が与えられます。 線分 P_iP_j を p:q に内分する点を Q_{i,j} とします。特に P_i=P_j ならば Q_{i,j}=P_i です。
1 \leq i \lt j \leq N を満たすすべての正整数組 (i,j) に対する Q_{i,j} についての凸包の面積を求めてください。
制約
- 2 \leq N \leq 10^5
- 1 \leq p \lt q \leq 10
- |X_i|\leq 10^7
- |Y_i|\leq 10^7
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
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 をこの順に空白区切りで一行で出力せよ。
入力例 1
4 1 2 -2 4 1 1 -3 -2 4 0
出力例 1
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} です。
入力例 2
3 3 4 11 -7 2 8 -4 18
出力例 2
0 1
凸包の面積が 0 であることもあります。
入力例 3
10 5 7 -3677189 -8603516 3324282 8371380 -4445534 -865546 -1235744 -6761030 2732080 -9194939 8510740 4384715 -7326815 2451526 -2079912 1054509 2072791 -8408897 -4437202 -5184973
出力例 3
6746232144385823 48
Score : 625 points
Problem Statement
There are N points P_1,P_2,\dots,P_N on the coordinate plane. The coordinates of point P_i are (X_i,Y_i).
You are given positive integers p,q. Let Q_{i,j} be the point that internally divides the segment P_iP_j in the ratio p:q. In particular, if P_i=P_j, then Q_{i,j}=P_i.
Find the area of the convex hull of Q_{i,j} for all pairs of positive integers (i,j) satisfying 1 \leq i \lt j \leq N.
Constraints
- 2 \leq N \leq 10^5
- 1 \leq p \lt q \leq 10
- |X_i|\leq 10^7
- |Y_i|\leq 10^7
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N p q X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
Output
It can be proved that, under the constraints of this problem, the area of the convex hull to be found is rational. When the area is represented as an irreducible fraction \dfrac{x}{y}\ (x \geq 0, y \geq 1), output x and y in this order, separated by a space, in one line.
Sample Input 1
4 1 2 -2 4 1 1 -3 -2 4 0
Sample Output 1
59 6
We have 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).
Their convex hull is the pentagon formed by connecting Q_{1,2},Q_{1,3},Q_{3,4},Q_{2,4},Q_{1,4} in this order, and its area is \frac{59}{6}.
Sample Input 2
3 3 4 11 -7 2 8 -4 18
Sample Output 2
0 1
The area of the convex hull may be 0.
Sample Input 3
10 5 7 -3677189 -8603516 3324282 8371380 -4445534 -865546 -1235744 -6761030 2732080 -9194939 8510740 4384715 -7326815 2451526 -2079912 1054509 2072791 -8408897 -4437202 -5184973
Sample Output 3
6746232144385823 48