AT_abc422_e.[ABC422E] Colinear

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在一个二维平面上有 $N$ 个点，其中 $N$ 是奇数。第 $i$ 个点的坐标是 $(x_i, y_i)$ 。所有点的坐标都互不相同。
请判断是否存在一条直线经过多于一半的 $N$ 个点，如果存在，请输出该直线。
对于满足约束条件的任意输入，如果存在满足条件的直线，则存在一组整数组 $a, b, c$ 使得直线方程可表示为 $ax+by+c=0$ ，且 $-10^{18} \leq a, b, c \leq 10^{18}$ ，并且 $(a, b, c) \neq (0, 0, 0)$ 。请输出这组 $a, b, c$ 。

输入格式

输入从标准输入读入，格式如下：

$N$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_N$ $y_N$

输出格式

如果不存在满足条件的直线，输出 No。
如果存在满足条件的直线，输出两行。第一行输出 Yes，第二行按照顺序输出 $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
```
输入#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

说明/提示

样例解释1

直线 $2x+y-8=0$ 经过了第 2 个和第 3 个点，所以满足条件。

样例解释2

不存在满足条件的直线。

约束条件

$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)$ 。
所有输入值均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页