AT_past202212_j.横断

通过率：0%

AC君温馨提醒

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

题目描述

给定平面上的两个点 $S(x_{\mathrm{s}}, y_{\mathrm{s}})$ 和 $T(x_{\mathrm{t}}, y_{\mathrm{t}})$ ，以及 $N$ 个四元组 $(P_i, Q_i, R_i, W_i)$ （ $1 \leq i \leq N$ ）。

请考虑如下的过程：

首先，在平面上从点 $S(x_{\mathrm{s}}, y_{\mathrm{s}})$ 到点 $T(x_{\mathrm{t}}, y_{\mathrm{t}})$ 上任选一条（有向）曲线 $C$ 。
接着，在 $1$ 到 $N$ 之间任选 $K$ 个不同的整数 $A_1, A_2, \ldots, A_K$ 。
对于每个 $i = 1, 2, \ldots, K$ $i = 1, 2, \dots, K$ ，执行以下操作：
- 如果曲线 $C$ 与直线 $P_{A_i}x + Q_{A_i}y = R_{A_i}$ 至少有一个公共点，你需要支付 $W_{A_i}$ 日元（日本的货币单位）。

请输出上述过程中你所需支付的最小总金额。

输入格式

输入按照如下格式从标准输入给出：

$N$ $K$ $x_{\mathrm{s}}$ $y_{\mathrm{s}}$ $x_{\mathrm{t}}$ $y_{\mathrm{t}}$
$P_1$ $Q_1$ $R_1$ $W_1$
$P_2$ $Q_2$ $R_2$ $W_2$
$\vdots$
$P_N$ $Q_N$ $R_N$ $W_N$

输出格式

输出答案。

输入输出样例

输入#1

输出#1

输入#2
```
2 2
0 0 0 0
1 2 3 4
2 4 6 8
```
输出#2
```
0
```

输入#3

20 17
-6 -77 40 99
-14 74 -48 27
-51 43 5 89
-39 -29 80 75
-55 59 17 39
-37 -68 38 62
14 31 43 49
49 -7 -65 13
-40 -45 36 32
-54 -43 99 77
-94 57 -22 12
-85 67 -46 72
95 68 55 67
-56 51 -38 22
32 -19 65 46
76 66 -53 8
35 -78 -41 30
-51 -85 24 64
45 -53 82 12
39 19 -52 86
-11 -67 -33 100

输出#3

说明/提示

样例解释 1

考虑选择沿 $x$ 轴从点 $S(-2, 0)$ 到 $T(2, 0)$ 的路径 $C$ ，并选择 $1$ 到 $4$ 中的整数 $2, 3, 4$ 作为这 $3$ 个不同的整数。那么：

曲线 $C$ 与直线 $P_2x + Q_2y = R_2$ （即 $y = 10$ ）没有公共点。
曲线 $C$ 与直线 $P_3x + Q_3y = R_3$ （即 $x = -1$ ）有公共点 $(-1, 0)$ ，因此你需要支付 $W_3 = 3$ 日元。
曲线 $C$ 与直线 $P_4x + Q_4y = R_4$ （即 $-x + y = 0$ ）有公共点 $(0, 0)$ ，因此你需要支付 $W_4 = 5$ 日元。

因此，你总共需要支付 $8$ 日元，这也是可能的最小花费。

样例解释 2

点 $S$ 和点 $T$ 可能是同一个点。同样， $P_ix + Q_iy = R_i$ 也可能对不同的 $i$ 来说是同一条直线。

数据范围与约定

$1 \leq N \leq 2 \times 10^5$
$1 \leq K \leq N$
$-10^9 \leq x_{\mathrm{s}}, y_{\mathrm{s}}, x_{\mathrm{t}}, y_{\mathrm{t}} \leq 10^9$
$-10^9 \leq P_i, Q_i, R_i \leq 10^9$
$1 \leq W_i \leq 10^9$
$P_i \neq 0$ 或 $Q_i \neq 0$
对所有 $i = 1, 2, \ldots, N$ ，点 $S$ 和点 $T$ 都不在直线 $P_ix + Q_iy = R_i$ 上。
所有输入均为整数。

由 ChatGPT 5 翻译

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

首页