Codeforces Educational 1C - Nearest Vectors

View as PDF

Submit solution


Points: 0.70 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
Codeforces Educational Round 1
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Bạn được cho một tập các vector trong mặt phẳng, các vector đều xuất phát từ gốc tọa độ. Nhiệm vụ của bạn là tìm cặp vector với số đo góc không định hướng giữa chúng là nhỏ nhất.

Góc không định hướng có giá trị trong khoảng từ ~0~ đến ~\pi~, là giá trị nhỏ nhất giữa ~2~ góc định hướng xuôi và ngược chiều kim đồng hồ. Ví dụ, ~2~ vector ngược chiều nhau có số đo góc bằng ~\pi~.

Input

  • Dòng đầu chứa một số nguyên ~n~ ~(2 \le n \le 100 \, 000)~ ~-~ số lượng vector.
  • ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~x_i~ và ~y_i~ ~(|x|, |y| \le 10 \, 000, x^2 + y^2 > 0)~ ~-~ tọa độ của vector thứ ~i~. Các vector được đánh số từ ~1~ đến ~n~ theo thứ tự nhập vào của input. Input đảm bảo rằng không có cặp vector nào chung hướng (nhưng vẫn có thể ngược hướng).

Output

In ra hai số nguyên ~a~ và ~b~ ~(a \neq b)~ ~-~ cặp chỉ số của hai vector có số đo góc không định hướng nhỏ nhất. Bạn có thể in hai số đó theo thứ tự bất kỳ. Nếu có nhiều kết quả, in ra cặp số bất kì trong các kết quả đó.

Sample 1

Input
4
-1 0
0 -1
1 0
1 1
Output
3 4

Sample 2

Input
6
-1 0
0 -1
1 0
1 1
-4 -5
-4 -6
Output
6 5

Comments

Please read the guidelines before commenting.


There are no comments at the moment.