SAC '22 Code Challenge 4 Junior P3 - Obligatory Triangle Problem

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

After setting a geometry problem, Max feels guilty and decides to ask you another.

Given N points in the form (x_i, y_i) that are not at the origin, find the angle on the unit circle and output the index of the one closest to angle A.

Can you help Max's guilt by solving this problem?

Constraints

0 \le A \le 359

-10^9 \le x_i, y_i \le 10^9

The data guarantee that the closest angle to A is at least 10^{-4} closer than any other angle.

Subtask 1 [10%]

N = 1

Subtask 2 [90%]

1 \le N \le 10^5

Input Specification

The first line will contain two space-separated integers, N and A, the number of points and angle, respectively.

The next N lines will contain two space-separated integers, x_i and y_i, the coordinates of the i^\text{th} point.

Output Specification

Output the 1-indexed index of the angle closest to angle A.

Sample Input 1

1 50
50 -30000

Sample Output 1

1

Sample Input 2

6 359
1 1
-1 -1
0 1
-1 0
5 1
5 -3

Sample Output 2

5

Comments

There are no comments at the moment.