← 返回题目列表

Codeforces · 135/B

B. 矩形和正方形

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

小Petya非常喜欢长方形,尤其是正方形。最近,他在飞机上收到了 8 点积分,这是他母亲送给他的礼物。这些点是成对不同的。 Petya 决定将它们分成两组,每组包含 4 个点,以便第一组中的点位于某个正方形的顶点,第二组中的点位于矩形的顶点上。前 8 个点中的每个点都应该属于一组。第二组中的矩形也是正方形是可以接受的。如果有多个分区,Petya 会对其中任何一个分区感到满意。帮他找到这样的分区。请注意,分区中的矩形和正方形应具有非零面积。图形的边不必与坐标轴平行,尽管情况可能如此。

输入

你有 8 对整数,每行一对——Petya 点的坐标。所有坐标的绝对值不超过104。保证没有两点重合。

输出

如果所需分区存在,则在第一输出行中打印“YES”(不带引号)。在第二行中,输出 4 个空格分隔的数字——来自输入的点索引,位于正方形的顶点。点从 1 开始编号。数字可以按任何顺序打印。在第三行中,以类似的格式打印位于矩形顶点的点的索引。所有打印的数字应成对不同。

如果所需的分区不存在,则第一行应包含单词“NO”(不带引号),之后不需要输出。

示例

输入 #1

0 0
10 11
10 0
0 11
1 1
2 2
2 1
1 2

输出 #1

YES
5 6 7 8
1 2 3 4

输入 #2

0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7

输出 #2

NO

输入 #3

0 0
4 4
4 0
0 4
1 2
2 3
3 2
2 1

输出 #3

YES
1 2 3 4
5 6 7 8

注意

请注意第三个示例:图形不一定必须与坐标轴平行。