分数: 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