Đây là bài chỉ nộp kết quả (Output Only).

Bitaro sẽ tham gia một cuộc thi bay nhào lộn. Máy bay của cậu giữ nguyên độ cao và bay qua các điểm kiểm tra. Ta biểu diễn khu vực bay bằng một mặt phẳng tọa độ. Có \(N\) điểm kiểm tra, đánh số từ \(1\) đến \(N\); điểm \(i\) có tọa độ \((X_i,Y_i)\).

Máy bay phải đi qua mỗi điểm kiểm tra đúng một lần theo cách sau:

1. Bitaro chọn một điểm kiểm tra làm điểm xuất phát.
2. Lặp lại \(N-1\) lần: chọn một điểm kiểm tra chưa được chọn, rồi bay thẳng từ điểm hiện tại tới điểm đó.
3. Khi đến điểm kiểm tra cuối cùng, chuyến bay kết thúc.

Trong bước \(2\), điểm xuất phát được coi là đã chọn. Máy bay phải bay thẳng giữa hai điểm kiểm tra liên tiếp; không được bay theo đường cong hoặc đổi hướng giữa chừng.

Lộ trình là một đường gấp khúc. Máy bay đổi hướng không quá \(N-2\) lần. Nếu góc của đường gấp khúc tại một điểm kiểm tra nhỏ, máy bay phải đổi hướng nhiều tại đó, làm tăng nguy cơ gặp sự cố. Vì vậy, Bitaro muốn góc nhỏ nhất tại \(N-2\) điểm kiểm tra, không kể điểm đầu và điểm cuối, lớn nhất có thể.

Cho tọa độ các điểm kiểm tra, hãy tìm thứ tự đi qua chúng sao cho góc nhỏ nhất của đường gấp khúc lớn nhất có thể.

Dữ liệu vào

Mỗi tệp đầu vào có dạng sau; tất cả các giá trị đều là số nguyên. \(Z_0\) là tham số dùng bởi trình chấm.

N Z_0
X_1 Y_1
...
X_N Y_N

Dữ liệu ra

Kết quả gồm \(N\) dòng. Dòng thứ \(k\) chứa số nguyên \(P_k\) \((1 \le P_k \le N)\), là điểm kiểm tra thứ \(k\) trong lộ trình. Điểm xuất phát là \(P_1\).

Nộp bài

Nộp các tệp kết quả output_01.txt, output_02.txt, ..., output_06.txt tương ứng với các tệp đầu vào input_01.txt, input_02.txt, ..., input_06.txt.

Ràng buộc

• \(3 \le N \le 1\,000\).
• \(\sqrt{X_i^2+Y_i^2} \le 10\,000\,000\) \((1 \le i \le N)\).
• \((X_i,Y_i) \ne (X_j,Y_j)\) \((1 \le i<j \le N)\).
• \(1 \le Z_0 \le 179\).

Thư viện

Tệp aerobatics.h trong gói phát cho thí sinh chứa hàm tính góc tạo bởi ba điểm:

double GetAngle(int xa, int ya, int xb, int yb, int xc, int yc);

Hàm trả về góc \(BAC\) theo đơn vị độ, với sai số đủ nhỏ. Chú ý thứ tự tham số:

• xa, ya là hoành độ và tung độ của điểm \(A\), tức đỉnh của góc.
• xb, yb là hoành độ và tung độ của điểm \(B\).
• xc, yc là hoành độ và tung độ của điểm \(C\).
• Nếu \(A\) trùng \(B\) hoặc \(A\) trùng \(C\), hành vi của hàm không được xác định.

Bạn có thể sử dụng và sửa đổi hàm GetAngle trong chương trình tạo lời giải của mình. Hàm được cung cấp giống hàm mà trình chấm sử dụng. Đây là thư viện hỗ trợ tạo kết quả, không phải hàm mà thí sinh cần cài đặt để nộp mã nguồn.

Chấm điểm

Mỗi tệp kết quả không hợp lệ được \(0\) điểm. Chẳng hạn, nếu dãy \(P_1,P_2,\ldots,P_N\) không phải là hoán vị của \(1,2,\ldots,N\), hoặc sai định dạng, tệp đó được \(0\) điểm.

Với kết quả hợp lệ, gọi \(Z\) là góc nhỏ nhất, tính bằng độ, tại \(N-2\) điểm trung gian của lộ trình, và \(S\) là điểm tối đa của tệp tương ứng. Điểm nhận được là:

• \(S\) nếu \(Z \ge Z_0\).
• \(S\times\dfrac{f(Z/180)}{f(Z_0/180)}\) nếu \(Z<Z_0\).

Trong đó, với \(0 \le \alpha \le 1\),

Điểm của bài là tổng điểm của sáu tệp, sau đó làm tròn đến số nguyên gần nhất.

Ví dụ

7 90
3 1
2 5
0 2
-1 6
-3 1
-1 -4
4 -2

5
3
1
7
6
4
2

Nguồn

JOI 2021 Spring Training Camp, Contest 1, JCIOI. Bản dịch tiếng Việt và hình trích từ đề chính thức theo CC BY-SA 4.0.