Hamilton Path
View as PDFTrên một mặt phẳng có n điểm có tọa độ nguyên ~(x_i, y_i)~ trong khoảng từ ~0~ đến ~10^6~. Khoảng cách giữa hai điểm có số thứ tự ~a~ và ~b~ là ~dist(a, b)~ được xác định như sau: ~|x_a - x_b| + |y_a - y_b|~ (khoảng cách tính bằng công thức này được gọi là khoảng cách Manhattan).
Chúng ta gọi một đường đi Hamiltonian là một hoán vị ~p_i~ của các số từ ~1~ đến ~n~. Chiều dài của đường đi này được tính theo công thức sau: $$\sum_{i=1}^{n-1}(dist(p_i, p_{i+1})) + dist(p_n, p_1)$$
Hãy tìm một đường đi Hamiltonian sao cho chiều dài của nó không vượt quá ~25 \times 10^8~. Lưu ý rằng bạn không cần tối ưu hóa chiều dài của đường đi.
Input
Dòng đầu tiên chứa số nguyên n ~(1 \leq n \leq 10^6)~.
Dòng thứ ~i+1~ chứa tọa độ của điểm thứ ~i~: ~x_i~ và ~y_i~ ~(0 \leq x_i, y_i \leq 10^6)~.
Đảm bảo rằng không có hai điểm nào trùng nhau.
Output
In ra hoán vị của các số ~p_i~ từ 1 đến ~n~ — đường đi Hamiltonian cần tìm.
Nếu có nhiều đáp án đúng, in bất kỳ một trong số chúng.
Đảm bảo rằng có ít nhất một đường đi thỏa mãn yêu cầu.
Sample Input 1
5
0 7
8 10
3 4
5 0
9 12
Sample Output 1
5 2 1 3 4
Comments
hi
This comment is hidden due to too much negative feedback. Show it anyway.