Tổng nhỏ nhất

Điểm: 6,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho $n$ vector trên mặt phẳng. Với mỗi vector $v_{i} = (x_{i}, y_{i})$ , bạn được phép biến đổi nó thành một trong bốn vector sau bằng cách đổi dấu một hoặc cả hai toạ độ:

$v_{i}^{(1)} = (x_{i}, y_{i})$
$v_{i}^{(2)} = (- x_{i}, y_{i})$
$v_{i}^{(3)} = (x_{i}, - y_{i})$
$v_{i}^{(4)} = (- x_{i}, - y_{i})$

Hãy chọn hai vector khác nhau $v_{i}$ và $v_{j}$ ( $i \neq j$ ), và hai chỉ số biến đổi $k_{1}, k_{2} \in {1, 2, 3, 4}$ , sao cho độ dài (giá trị tuyệt đối) của tổng hai vector $| v_{i}^{(k_{1})} + v_{j}^{(k_{2})} |$ là nhỏ nhất có thể.

Dữ liệu vào

Dòng đầu chứa số nguyên $n$ .
$n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_{i}$ , $y_{i}$ — toạ độ của vector $v_{i}$ .

Dữ liệu ra

In ra bốn số nguyên $i k_{1} j k_{2}$ trên một dòng, cách nhau bởi dấu cách, sao cho $| v_{i}^{(k_{1})} + v_{j}^{(k_{2})} |$ là nhỏ nhất. Nếu có nhiều phương án cho cùng giá trị nhỏ nhất, bạn có thể in ra một phương án bất kỳ.

Ràng buộc

$2 \leq n \leq 10^{5}$
$- 10^{4} \leq x_{i}, y_{i} \leq 10^{4}$

Ví dụ

Input	Output	Giải thích
5 3 2 -4 7 -6 0 -8 4 5 1	5 1 3 1	Chọn $v_{5} = (5, 1)$ (biến đổi 1) và $v_{3} = (- 6, 0)$ (biến đổi 1). Tổng $(- 1, 1)$ có độ dài $\sqrt{2}$ . Có thể có nhiều đáp án khác cùng đạt giá trị này.
5 -7 -3 9 0 -8 6 7 -8 4 -5	4 1 3 1	Chọn $v_{4} = (7, - 8)$ (biến đổi 1) và $v_{3} = (- 8, 6)$ (biến đổi 1). Tổng $(- 1, - 2)$ có độ dài $\sqrt{5}$ .

Bình luận

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