AT_jag2018summer_day2_f Point Sequences

Takahashi 君每年都会为 Aoki 君准备整数序列作为生日礼物。今年，他决定赠送一组平面上的点序列。 首先，他生成了三个点序列：$(a_0, a_1, \ldots, a_{N-1})$，$(b_0, b_1, \ldots, b_{N-1})$，和 $(c_0, c_1, \ldots, c_{N-1})$，还生成了一个初始点 $d_0$。然后，按以下方法依次生成点 $d_1, d_2, \ldots, d_N$： - 对于每一个 $i = 0, 1, \ldots, N-1$，$d_{i+1}$ 被定义为通过点 $a_i$ 和 $b_i$ 的直线与通过点 $c_i$ 和 $d_i$ 的直线的交点。 然而，可能存在某些情形，使得点 $d_{i+1}$ 无法定义。比如，当两条线重合时，交点无穷多。 Takahashi 君想确定最小的 $i$，使得 $d_{i+1}$ 无法定义。具体来说，在下列条件下，$d_{i+1}$ 无法被定义： - $c_i$ 与 $d_i$ 是同一个点 - 由 $a_i, b_i, c_i$ 和 $d_i$ 确定的两条直线相同或平行 题目保证对于所有 $i$，$a_i$ 和 $b_i$ 是不同的点。 在接下来的描述中，点 $p$ 的 $x$ 坐标和 $y$ 坐标分别表示为 $p.x$ 和 $p.y$。

输入为标准输入，格式如下： > $N$ $d_0.x$ $d_0.y$ $a_0.x$ $a_0.y$ $b_0.x$ $b_0.y$ $c_0.x$ $c_0.y$ $a_1.x$ $a_1.y$ $b_1.x$ $b_1.y$ $c_1.x$ $c_1.y$ $ \ldots $ $a_{N-1}.x$ $a_{N-1}.y$ $b_{N-1}.x$ $b_{N-1}.y$ $c_{N-1}.x$ $c_{N-1}.y$

输出最小的 $i$ 使得 $d_{i+1}$ 无法定义。如果所有点都可以被定义，则输出 $N$。

- $1 \leq N \leq 100,000$ - 点的坐标范围：$|a_i.x|, |a_i.y|, |b_i.x|, |b_i.y|, |c_i.x|, |c_i.y| \leq 1,000$ - 初始点 $d_0$ 的坐标范围：$|d_0.x|, |d_0.y| \leq 1,000$ - 保证所有 $i$ 均有 $a_i \neq b_i$ - 输入值全为整数。 **本翻译由 AI 自动生成**