Temple Construction

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

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 N 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 K. Formally, let A be the area of a temple with corners in the given set. The temple Aqua wants is the temple such that the value |A-K| is minimized. Please help her find such a temple.

Input Specification

The first line will contain 2 integers N and K, the number of points in the set and Aqua's favourite number.

The next N lines will each contain 2 integers x_i, y_i, denoting the location of the i^\text{th} point.

Output Specification

On the first line, output 4 distinct integers a, b, c, d, 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.


For all subtasks:

4 \le N \le 800

0 \le K \le 10^{18}

1 \le x_i, y_i \le 10^9

All points of the set are pairwise distinct, and no 3 points are collinear.

Subtask 1 [30%]

K = 10^{18}

Subtask 2 [10%]

4 \le N \le 100

Subtask 3 [20%]

4 \le N \le 300

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 K for its area! The optimal temple to build is thus 1 2 4 5, which has area 15.

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 12 (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 12.


There are no comments at the moment.