← 返回题目列表

AtCoder · abc422_e

H. 共线

中文机器翻译题面 查看原题

分数: 450 点

问题陈述

有 N 点位于二维平面上。 N 是奇数。的 i第一个点位于 (x_i, y_i)。所有点坐标都是不同的。
判断是否存在经过一半以上的直线 N 点,如果有,则输出。
对于任意满足约束的输入,如果存在满足条件的行,则可以表示为 ax+by+c=0 使用整数 a,b,c 与 -10^{18} \leq a,b,c \leq 10^{18} (其中 (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
  • If 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.
如果存在满足条件的行,则输出两行。第一行,输出 Yes,在第二行,输出 a,b,c 按此顺序用空格分隔。 a,b,c 必须满足 -10^{18} \leq a,b,c \leq 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 通过 2nd 和 3rd点,所以满足条件。


示例输入 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