No.3074 Divide Points Fairly
Problem Statement
You are given $2N$ distinct lattice points $(x_1, y_1), \cdots, (x_{2N},y_{2N})$ on the coordinate plane. Find $1$ line $L$ that satisfies all of the following conditions.
None of the given lattice points lie on the line $L$.
Each of the $2$ half-planes divided by the line $L$ contains exactly $N$ of the given lattice points.
The equation of the line $L$ can be written as $ax+by+c = 0$ using a tuple of integers $(a, b, c)$ such that $|a| \leq 10^5, |b| \leq 10^5, |c| \leq 2\times 10^{10}$.
It can be shown that at least $1$ such line $L$ exists under the constraints of this problem.
Constraints
$1\leq N \leq 5\times 10^4$
$|x_i| \leq 10^5$ $(1\leq i \leq 2N)$
$|y_i| \leq 10^5$ $(1\leq i \leq 2N)$
$(x_i, y_i) \neq (x_j, y_j)$ $(i \neq j)$
All input values are integers.
Input
$N$
$x_1$ $y_1$
$\vdots$
$x_{2N}$ $y_{2N}$
Output
$a$ $b$ $c$
Let $ax+by+c=0$ be the equation of the line $L$ you found, and output the integers $a, b, c$.
$|a| \leq 10^5, |b| \leq 10^5, |c| \leq 2\times 10^{10}$ must hold.
Note that an output with $a = b = 0$ results in WA.
Notes
This problem uses a special judge. There may be multiple solutions. The behavior of the judge is undefined for submissions that do not follow the output format.
Sample
Sample 1
Input
2 1 1 2 1 3 2 3 4
Output
1 1 -4
The figure shows the $4$ input points and the line $x + y -4 = 0$.
None of the input lattice points lie on the line $L$.
The line $L$ divides the input lattice points into groups of $2$ points each.
$|1|\leq 10^5, |-4| \leq 2\times 10^{10}$
Therefore, this output is $1$ of the lines $L$ satisfying the conditions.
Other outputs such as
-3 -3 12
2 0 -5
also satisfy the conditions.
Sample 2
Input
2 1 1 2 1 1 2 2 2
Output
2 0 -3
Sample 3
Input
3 -2 -7 -6 2 5 -2 0 6 6 -9 -2 0
Output
2 1 3
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
hamamu