4491: C. Grass
内存限制：256 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：Special Judge
上传者：
提交：0
通过：0
题目描述
Charles the Rabbit likes eating grass. As the saying goes, rabbits do not eat the grass by their burrows. Therefore, Charles has to go outside his burrow every day to look for grass to eat.
One day, Charles comes to a two-dimensional plane with many distinct points. He can choose a point A and another four points B, C, D, E to connect with A to form four segments. We consider these four segments as a clump of grass if they meet the following condition:
For example, in the picture below, (1) is a clump of grass, but (2) is not one as the intersection of segments AC and AE is not only a single point A.
- Any two of the four segments have only a single point of intersection A between them.
Given n points on a plane, Charles wants to know whether there exists a clump of grass. If so, help him find a certain one.
输入格式
The first line contains an integer T (1 ≤ T ≤ 120), indicating the number of test cases.
The first line of each test case contains an integer n (1 ≤ n ≤ 25000), indicating the number of points.
Each of the following n lines contains two integers x,y (-107 ≤ x,y ≤ 107), indicating that the coordinates of the point are (x,y). It is guaranteed that all points are distinct.
It is guaranteed that ∑ n ≤ 105 over all test cases.
The first line of each test case contains an integer n (1 ≤ n ≤ 25000), indicating the number of points.
Each of the following n lines contains two integers x,y (-107 ≤ x,y ≤ 107), indicating that the coordinates of the point are (x,y). It is guaranteed that all points are distinct.
It is guaranteed that ∑ n ≤ 105 over all test cases.
输出格式
For each test case, if there does not exist a clump of grass, output NO in a single line.
Otherwise, output YES in the first line. Then output two integers separated by a space in the second line, indicating the coordinates of point A. Then output two integers separated by a space in each of the third to sixth lines, indicating the coordinates of the other four points B, C, D, E.
If there is more than one clump of grass, output any.
Otherwise, output YES in the first line. Then output two integers separated by a space in the second line, indicating the coordinates of point A. Then output two integers separated by a space in each of the third to sixth lines, indicating the coordinates of the other four points B, C, D, E.
If there is more than one clump of grass, output any.
输入样例 复制
3
5
0 0
1 1
1 -1
-1 1
-1 -1
3
1 1
4 5
1 4
5
1 0
2 0
3 0
4 0
5 0
输出样例 复制
YES
0 0
1 1
1 -1
-1 1
-1 -1
NO
NO