E - Colinear Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

2 次元平面上に N 個の点があります。N は奇数です。 i 番目の点は (x_i, y_i) にあります。全ての点の座標は相異なります。
N 個の点のうち過半数を通る直線が存在するかを判定して、存在すればそれを出力してください。
なお、制約を満たすどのような入力においても、条件を満たす直線が存在する場合、その直線は -10^{18} 以上 10^{18} 以下の整数 a,b,c を用いて ax+by+c=0 と表すことができます。(ただし (a,b,c) \neq (0,0,0)) この a,b,c を出力してください。

制約

  • 3 \leq N \leq 5 \times 10^5
  • N は奇数
  • -10^8 \leq x_i \leq 10^8
  • -10^8 \leq y_i \leq 10^8
  • i \neq j ならば (x_i, y_i) \neq (x_j, y_j)
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
x_1 y_1
x_2 y_2
\vdots
x_N y_N

出力

条件を満たす直線が存在しない場合は No を出力せよ。
条件を満たす直線が存在する場合は 2 行出力せよ。1 行目には Yes を出力して、2 行目には a,b,c をこの順に空白区切りで出力せよ。a,b,c は -10^{18} 以上 10^{18} 以下かつ (a,b,c) \neq (0,0,0) である必要がある点に注意せよ。
答えが複数ある場合はどれを出力しても正答とみなされる。

入力例 1

3
1 1
3 2
2 4

出力例 1

Yes
2 1 -8

直線 2x+y-8=0 は 2 番目の点と 3 番目の点を通るので条件を満たします。

入力例 2

5
5 2
1 3
2 6
4 4
5 4

出力例 2

No

条件を満たす直線は存在しません。

入力例 3

11
-9374372 85232388
-60705467 86198234
-7475320 80628487
98066347 -23868213
-12177678 85284287
30535572 -35358356
51324557 22410787
28854279 44658587
-28804873 82911971
65052073 8819187
-67744430 68365758

出力例 3

Yes
4655800 4702358 -344340416016346

Score : 450 points

Problem Statement

There are N points on a two-dimensional plane. N is odd. The i-th point is at (x_i, y_i). All point coordinates are distinct.
Determine whether there exists a line passing through more than half of the N points, and if so, output it.
For any input satisfying the constraints, if a line satisfying the condition exists, it can be expressed as ax+by+c=0 using integers a,b,c with -10^{18} \leq a,b,c \leq 10^{18} (where (a,b,c) \neq (0,0,0)). Output these a,b,c.

Constraints

  • 3 \leq N \leq 5 \times 10^5
  • N is odd.
  • -10^8 \leq x_i \leq 10^8
  • -10^8 \leq y_i \leq 10^8
  • If i \neq j, then (x_i, y_i) \neq (x_j, y_j).
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
\vdots
x_N y_N

Output

If no line satisfying the condition exists, output No.
If a line satisfying the condition exists, output two lines. On the first line, output Yes, and on the second line, output a,b,c in this order separated by spaces. a,b,c must satisfy -10^{18} \leq a,b,c \leq 10^{18} and (a,b,c) \neq (0,0,0).
If there are multiple solutions, any of them will be considered correct.

Sample Input 1

3
1 1
3 2
2 4

Sample Output 1

Yes
2 1 -8

The line 2x+y-8=0 passes through the 2nd and 3rd points, so it satisfies the condition.

Sample Input 2

5
5 2
1 3
2 6
4 4
5 4

Sample Output 2

No

No line satisfying the condition exists.

Sample Input 3

11
-9374372 85232388
-60705467 86198234
-7475320 80628487
98066347 -23868213
-12177678 85284287
30535572 -35358356
51324557 22410787
28854279 44658587
-28804873 82911971
65052073 8819187
-67744430 68365758

Sample Output 3

Yes
4655800 4702358 -344340416016346