To celebrate her birthday In honour of the glorious Axis Order, Aqua has decided to construct a new temple so that more people are able to worship her. Since she is incapable of handling complex shapes, Aqua added that her new temple must be a quadrilateral. Furthermore, to silence pesky rumours that followers of the Axis Order are crazy in the head, Aqua's new temple must also not be self-intersecting. Currently, she has a set of two dimensional points which denote the possible locations of the corners of her temple. To maximize the glamour of this temple, Aqua would like to identify the temple with area closest to her favourite number . Formally, let be the area of a temple with corners in the given set. The temple Aqua wants is the temple such that the value is minimized. Please help her find such a temple.
Input Specification
The first line will contain integers and , the number of points in the set and Aqua's favourite number.
The next lines will each contain integers , denoting the location of the point.
Output Specification
On the first line, output distinct integers , denoting the indices of the corners of the temple with area closest to Aqua's favourite number. You must print these indices such that they represent the corners of the temple in clockwise or counterclockwise order. If there are multiple such temples, you may print any of them.
Constraints
For all subtasks:
All points of the set are pairwise distinct, and no points are collinear.
Subtask 1 [30%]
Subtask 2 [10%]
Subtask 3 [20%]
Subtask 4 [40%]
No additional constraints.
Sample Input 1
6 1000000000000000000
4 5
2 3
3 2
7 1
8 5
6 4
Sample Output 1
1 2 4 5
Explanation for Sample 1
Aqua's favourite number is so huge that no possible temple can have for its area! The optimal temple to build is thus 1 2 4 5
, which has area .
Note that output 4 2 1 5
would also be accepted.
You do not need to pass the following sample cases to pass Subtask 1.
Sample Input 2
4 0
1 4
4 4
5 1
7 6
Sample Output 2
1 3 2 4
Explanation for Sample 2
Pay careful attention to the order you output your selected indices. In this case, outputs such as 1 2 3 4
or 1 2 4 3
would not be accepted since they represent different temples from the optimal one.
Sample Input 3
8 12
1 2
8 8
5 3
3 7
6 6
5 10
9 1
10 4
Sample Output 3
2 7 5 4
Explanation for Sample 3
Below is a diagram illustrating the solution to this case:
The selected temple has area exactly (Aqua's favourite number), and it is the one Aqua dreams about non-stop!
Note that output 1 3 4 7
would be accepted as well, since it also represents a temple with area .
Comments