← 返回题目列表

AtCoder · jag2018summer_day2_f

F. 点序列

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

分数: 100 点

问题陈述

高桥君每年都会向青木君发送整数序列作为他的生日礼物。 但今年,高桥君计划将二维平面上的点序列发送给青木君。

首先,他让 3 点序列: (a_0, a_1, ..., a_{N-1}), (b_0, b_1, ..., b_{N-1}),和 (c_0, c_1, ..., c_{N-1}),并提出了一个观点 d_0。 然后他提出要点 d_1, d_2, ..., d_N 按顺序如下:

  • 对于每个 i = 0, 1, ..., {N-1}, d_{i+1} 定义为两条线的交点:穿过的线 a_i 和 b_i,以及经过的线 c_i 和 d_i.

有可能发生一个点 d_{i+1} 无法定义某些 i。 例如,当两条线相同时,有无数个交点。

高桥君想知道最小的 i 这样 d_{i+1} 无法定义。 准确地说, 如果满足以下任一条件,则无法定义 d_{i+1} 。

  • c_i = d_i
  • 两行由 a_i, b_i, c_i,和 d_i 相同,或平行。

保证 a_i \neq b_i 对于所有人 i.

请注意,在以下部分中, x- 和 y- 点的坐标 p 表示为 p.x 和 p.y。

约束

  • 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.x|, |d_0.y| \leq 1000
  • a_i \neq b_i
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

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

6
0 0
10 -10 10 10 10 0
0 10 20 10 10 10
0 -10 0 -100 0 10
0 0 0 -100 0 0
0 0 0 1 0 0
31 14 15 92 65 35

示例输出 1

3

示例输入 2

11
0 0
299 0 299 1 3 1
1 0 1 1 300 100
299 0 299 1 3 1
1 0 1 1 300 100
299 0 299 1 3 1
1 0 1 1 300 100
299 0 299 1 3 1
1 0 1 1 300 100
299 0 299 1 3 1
1 0 1 1 300 100
0 0 3 1 3 1

示例输出 2

10