Codeforces Educational 1C - Nearest Vectors

Xem dạng PDF

Gửi bài giải


Điểm: 0,70 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Người đăng:
Nguồn bài:
Codeforces Educational Round 1
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.