問題一覧 > 通常問題

No.3074 Divide Points Fairly

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 44
作問者 : 👑 binap / テスター : 👑 p-adic 👑 hamamu 👑 qand
お気に入りにしたユーザー ProblemId : 11948 / 自分の提出
問題文最終更新日: 2025-03-24 23:57:31
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 462 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。