题目背景
道不同不相为谋。
.cilohocohc 喜欢吃蛋糕,尤其是巧克力蛋糕。
LeverImmy 送了一个超级大的巧克力蛋糕给她做生日礼物,蛋糕上面点缀着许多巧克力布丁。
.cilohocohc 一个人肯定是吃不完那么大一个蛋糕的,于是她要 LeverImmy 帮她蛋糕切成两块,使得两块蛋糕上的布丁数之比为 a:b。
蛋糕可以抽象为一个二维平面;而做蛋糕的作坊很缺心眼,因此每个布丁都很小,可以看成二维平面上的一个 整点。
LeverImmy 的刀技非常高超,所以他准备秀一下,他只会以一个 斜率不小于 1 ,不大于 1012 的一次函数图像 为轮廓在蛋糕上划一刀。
他想考考聪明的你,如果是你,你会怎么划?
题目描述
已知 n 以及 a,b,求一个一次函数 f(x)=k(x−x0)+y0(1≤k≤1012),使得 f(x) 将平面内的 n 个点恰好分为个数之比 a:b 的两部分。
如果你不知道一次函数为什么要这样表示,这里有 点斜式 的定义。
输入格式
第一行三个整数 n,a,b,表示点的个数以及你要分成两部分的比例。
接下来的 n 行,第 i 行两个整数 xi,yi 表示平面上的点 (xi,yi)。
数据保证 任意两个点不重合。
输出格式
输出数据共一行三个整数,分别表示题目中的 k,x0,y0。
请务必保证 1≤k≤1012,−105≤x0,y0≤105。
如果有点 恰好 落在你给的直线上,我们视作其位于直线 上方。
2 1 1
0 1
1 0
1 0 0
提示
本题采用 捆绑测试。
Subtask 1 (10 pts): 保证 n∈{2,3};
Subtask 2 (30 pts): 保证 ∣xi∣,∣yi∣≤10;
Subtask 3 (60 pts): 保证 2≤n≤105,0≤∣xi∣,∣yi∣≤105。
对于所有数据,保证 (a+b)∣n 且 ab=0。
Special Judge
本题采用 Special Judge。
spj 返回信息一览:
Your answer is correct!
:你的结果是正确的;
Your answer is wrong, expected ratio as a : b, found A : B.
:你的函数有问题,它把所有的点分割成了 A:B 的两部分而不是 a:b 的两部分;
Oops, data out of range!
:你所给出的点的横纵坐标,或是斜率,在题目要求的范围外。
注意,你在 赛时 并不能看到 Special Judge 的返回结果。