## DMOPC '21 Contest 1 P5 - Perfect Cross

View as PDF

Points: 25 (partial)
Time limit: 5.0s
Memory limit: 256M

Author:
Problem types

Bob the Builder loves building perfect crosses in 2-D planes — two lines where the counterclockwise angles of each line to the -axis are exactly and . There are points in the plane, and Bob would like to pick two pairs of points to draw a perfect cross. However, real-life is harsh, and it may be impossible to construct a perfect cross from the points given. Furthermore, Bob can only access points that are within steps from his camp location, each step one unit in an axis-aligned direction.

Let the distance between two lines be defined as the minimal absolute degree measure you need to rotate one of the lines such that both lines share the same slope. For queries of camp locations , help Bob find two pairs of accessible points that are as close to a perfect cross as possible — one pair should be as close to a line as possible, and the other pair closest to a line. Each pair of points should consist of two distinct points, although it is allowed to use the same points for different pairs.

#### Constraints

All points are pairwise distinct.

There are at least two accessible points in each query.

#### Input Specification

The first line contains integers , , and .

The next lines each contain integers and .

The next lines each contain integers and .

#### Output Specification

For each query, output integers on a single line: . These should satisfy and .

The -th, -th, -th, and -th points must all be within axis-aligned steps from the query location.

Furthermore, over all accessible points, the line connecting the -th and -th point should be as close to a line as possible, and the line connecting the -th and -th point should be as close to a line as possible.

If there are multiple such choices of points satisfying all of the properties above, any one of them will be accepted.

#### Sample Input

5 3 5
3 1
1 -3
1 -2
-1 2
-3 0
3 1
-1 1
5 -1

#### Sample Output

1 3 4 3
5 4 3 5
3 1 1 3

#### Explanation

Below is a diagram of the cross chosen in the first query:

Then, a diagram of the second cross. Here, an equally correct choice for the second line is marked in blue:

Finally, a diagram of the cross chosen in the third query. Since there are only two accessible points, we must choose them for both lines of the cross: