CF135B.Rectangle and Square
普及/提高-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Little Petya very much likes rectangles and especially squares. Recently he has received 8 points on the plane as a gift from his mother. The points are pairwise distinct. Petya decided to split them into two sets each containing 4 points so that the points from the first set lay at the vertexes of some square and the points from the second set lay at the vertexes of a rectangle. Each point of initial 8 should belong to exactly one set. It is acceptable for a rectangle from the second set was also a square. If there are several partitions, Petya will be satisfied by any of them. Help him find such partition. Note that the rectangle and the square from the partition should have non-zero areas. The sides of the figures do not have to be parallel to the coordinate axes, though it might be the case.
小佩佳非常喜欢矩形,尤其是正方形。最近,他从母亲那里收到了平面上的 8 个点作为礼物。这些点两两互异。佩佳决定将这 8 个点划分为两个集合,每个集合包含 4 个点,使得第一个集合中的点恰好构成某个正方形的四个顶点,而第二个集合中的点恰好构成某个矩形的四个顶点。初始的 8 个点中的每一个都必须且仅属于其中一个集合。允许第二个集合所构成的矩形本身也是一个正方形。若存在多种划分方式,佩佳接受其中任意一种即可。请你帮助他找到这样一种划分。注意:划分所得的矩形与正方形的面积均必须为非零值。这些图形的边不必与坐标轴平行(尽管也可能恰好平行)。
输入格式
You are given 8 pairs of integers, a pair per line — the coordinates of the points Petya has. The absolute value of all coordinates does not exceed 104. It is guaranteed that no two points coincide.
给你 8 对整数,每行一对——即小彼佳所标记的点的坐标。所有坐标的绝对值均不超过 104。保证任意两个点不重合。
输出格式
Print in the first output line "YES" (without the quotes), if the desired partition exists. In the second line output 4 space-separated numbers — point indexes from the input, which lie at the vertexes of the square. The points are numbered starting from 1. The numbers can be printed in any order. In the third line print the indexes of points lying at the vertexes of a rectangle in the similar format. All printed numbers should be pairwise distinct.
If the required partition does not exist, the first line should contain the word "NO" (without the quotes), after which no output is needed.
如果存在所要求的划分,在第一行输出 "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
说明/提示
Pay attention to the third example: the figures do not necessarily have to be parallel to the coordinate axes.
请注意第三个例子:图形不一定与坐标轴平行。
输入解题思路,AI测评打分。不知道怎么写?