luogu#P6614. 蛋糕 Cake

蛋糕 Cake

题目背景

道不同不相为谋。

.cilohocohc\text{.cilohocohc} 喜欢吃蛋糕,尤其是巧克力蛋糕。

LeverImmy\text{LeverImmy} 送了一个超级大的巧克力蛋糕给她做生日礼物,蛋糕上面点缀着许多巧克力布丁。

.cilohocohc\text{.cilohocohc} 一个人肯定是吃不完那么大一个蛋糕的,于是她要 LeverImmy\text{LeverImmy} 帮她蛋糕切成两块,使得两块蛋糕上的布丁数之比为 a:ba : b

蛋糕可以抽象为一个二维平面;而做蛋糕的作坊很缺心眼,因此每个布丁都很小,可以看成二维平面上的一个 整点

LeverImmy\text{LeverImmy} 的刀技非常高超,所以他准备秀一下,他只会以一个 斜率不小于 11 ,不大于 101210^{12} 的一次函数图像 为轮廓在蛋糕上划一刀。

他想考考聪明的你,如果是你,你会怎么划?

题目描述

已知 nn 以及 a,ba, b,求一个一次函数 f(x)=k(xx0)+y0(1k1012)f(x) = k(x - x_0) + y_0 (1 \le k \le 10^{12}),使得 f(x)f(x) 将平面内的 nn 个点恰好分为个数之比 a:ba : b 的两部分。

如果你不知道一次函数为什么要这样表示,这里有 点斜式 的定义。

输入格式

第一行三个整数 n,a,bn, a, b,表示点的个数以及你要分成两部分的比例。

接下来的 nn 行,第 ii 行两个整数 xi,yix_i, y_i 表示平面上的点 (xi,yi)(x_i, y_i)

数据保证 任意两个点不重合

输出格式

输出数据共一行三个整数,分别表示题目中的 k,x0,y0k, x_0, y_0

请务必保证 1k1012,105x0,y01051 \le k \le 10^{12}, -10^5 \le x_0, y_0 \le 10^{5}

如果有点 恰好 落在你给的直线上,我们视作其位于直线 上方

2 1 1
0 1
1 0
1 0 0

提示

本题采用 捆绑测试

Subtask 1 (10 pts):\text{Subtask 1 (10 pts)}: 保证 n{2,3}n \in \{2, 3\}

Subtask 2 (30 pts):\text{Subtask 2 (30 pts)}: 保证 xi,yi10\left|x_i\right|, \left|y_i\right| \le 10

Subtask 3 (60 pts):\text{Subtask 3 (60 pts)}: 保证 2n1052 \le n \le 10^50xi,yi1050 \le \left|x_i\right|, \left|y_i\right| \le 10^5

对于所有数据,保证 (a+b)n(a + b) | nab0ab \neq 0


Special Judge

本题采用 Special Judge\text{Special Judge}

spj 返回信息一览:

Your answer is correct!:你的结果是正确的;

Your answer is wrong, expected ratio as a : b, found A : B.:你的函数有问题,它把所有的点分割成了 A:BA : B 的两部分而不是 a:ba : b 的两部分;

Oops, data out of range!:你所给出的点的横纵坐标,或是斜率,在题目要求的范围外。

注意,你在 赛时 并不能看到 Special Judge 的返回结果。