P6614 Cake Cake

> Those who do not share the same values cannot work together. $\text{.cilohocohc}$ likes eating cake, especially chocolate cake. $\text{LeverImmy}$ gave her a super huge chocolate cake as a birthday present, with many chocolate puddings decorating the cake. $\text{.cilohocohc}$ definitely cannot finish such a big cake by herself, so she wants $\text{LeverImmy}$ to help her cut the cake into two pieces, such that the ratio of the number of puddings on the two pieces is $a : b$. The cake can be abstracted as a 2D plane; and the workshop that made the cake is rather careless, so each pudding is very small and can be regarded as an **integer lattice point** on the 2D plane. $\text{LeverImmy}$ has excellent knife skills, so he plans to show off. He will only make one cut along the graph of a **linear function with slope not less than $1$ and not greater than $10^{12}$**. He wants to test your intelligence: if it were you, how would you cut it?

Given $n$ and $a, b$, find a linear function $f(x) = k(x - x_0) + y_0 \ (1 \le k \le 10^{12})$ such that $f(x)$ divides the $n$ points in the plane into two parts whose counts are in the ratio $a : b$. If you do not know why a linear function is written in this form, here is the definition of [point-slope form](https://baike.baidu.com/item/%E7%82%B9%E6%96%9C%E5%BC%8F/921468?fr=aladdin).

The first line contains three integers $n, a, b$, representing the number of points and the ratio you want to split into. The next $n$ lines each contain two integers $x_i, y_i$, representing the point $(x_i, y_i)$ on the plane. The testdata guarantees that **no two points coincide**.

Output one line with three integers, representing $k, x_0, y_0$ in the statement. You must ensure that $1 \le k \le 10^{12}, -10^5 \le x_0, y_0 \le 10^{5}$. If a point lies **exactly** on the line you give, we consider it to be **above** the line.

This problem uses **bundled tests**. $\text{Subtask 1 (10 pts)}:$ guaranteed $n \in \{2, 3\}$. $\text{Subtask 2 (30 pts)}:$ guaranteed $\left|x_i\right|, \left|y_i\right| \le 10$. $\text{Subtask 3 (60 pts)}:$ guaranteed $2 \le n \le 10^5$, $0 \le \left|x_i\right|, \left|y_i\right| \le 10^5$. For all testdata, it is guaranteed that $(a + b) | n$ and $ab \neq 0$. --- #### Special Judge **This problem uses $\text{Special Judge}$.** List of spj return messages: `Your answer is correct!`: your result is correct. `Your answer is wrong, expected ratio as a : b, found A : B.`: your function is incorrect; it splits all points into two parts with ratio $A : B$ instead of $a : b$. `Oops, data out of range!`: the coordinates or slope you provided are outside the required range. Note that during the **contest**, you cannot see the return message from Special Judge. Translated by ChatGPT 5