← 返回题目列表

Codeforces · 618/C

C. 星座

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

Cat Noku 获得了一张夜空地图。在这张地图上,他发现了一个星座,有n颗星星,编号从1到n。对于每个 i,第 i 个恒星位于坐标 (xi, yi) 处。没有两颗星星位于同一位置。

晚上,Noku 要去看看夜空。他想找到三颗不同的星星并形成一个三角形。三角形的面积必须为正。此外,所有其他恒星必须严格位于该三角形之外。他找不到答案,需要你的帮助。你的工作是找到三颗星的索引,它们可以形成满足所有条件的三角形。

保证不存在所有星星都位于该线上的线。可以证明,如果满足前面的条件,则该问题存在解。

输入

输入的第一行包含一个整数 n (3 ≤ n ≤ 100 000)。

接下来的 n 行每行包含两个整数 xi 和 yi (- 109 ≤ xi, yi ≤ 109)。

保证没有两颗星星位于同一点,并且不存在一条线使得所有星星都位于该线上。

输出

在一行上打印三个不同的整数 - 形成满足问题中所述条件的三角形的三个点的索引。

如果有多个可能的答案,您可以打印其中任何一个。

示例

输入 #1

3
0 1
1 0
1 1

输出 #1

1 2 3

输入 #2

5
0 0
0 2
2 0
2 2
1 1

输出 #2

1 3 5

注意

在第一个示例中,我们可以按任意顺序打印三个索引。

在第二个示例中,我们有以下图片。

请注意,由起点 1、4 和 3 形成的三角形不满足问题中所述的条件,因为点 5 并不严格位于该三角形之外(它位于其边界上)。