Background

This is an output-only problem.

SPJ modified by wlzhouzhuan.

Problem Description

On a 2D Cartesian coordinate plane, there are $N$ points $(X_i, Y_i)$. Xiao B starts from one point, chooses any point as the destination, walks to it along a straight-line path, and repeats this process $N - 1$ times. It is not hard to see that this will form a polyline consisting of $N$ line segments. For every point except the first and the last, an angle $\alpha_i\ (2 \le i \le n - 1)$ is formed (the one that is $\le 180^\circ$; $i$ denotes the $i$-th visited point). Xiao B asks you to maximize the following expression by planning the visiting order of the points along the polyline:

Input Format

The first line contains two integers $N, Z_0$, representing the number of points and the scoring parameter (see Constraints and Notes, and the evaluation description below).

The next $N$ lines each contain two integers $X_i, Y_i$, representing a point.

Output Format

Output $N$ lines, each containing an integer $P_k$, representing the index of the $k$-th visited point.

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

5
3
1
7
6
4
2

Hint

Sample 1 Explanation

As shown in the figure below:

The smallest angle is at point $6$, which is $68.19859\cdots^\circ$. With $Z_0 = 90$ and the scoring parameter description in the evaluation method below, this output can get a score of $61.5\%$.

Constraints and Notes

For $100\%$ of the testdata, $3 \le N \le 1000$, $\sqrt{X_i^2 + Y_i^2} \le 10^7$, no two points coincide, and $1 \le Z_0 \le 179$.

In particular, this is an output-only problem, with a total of $6$ test cases:

• The input files are input_01.txt to input_06.txt.
• The output files are output_01.txt to output_06.txt.
• For each test case, its $N$, $Z_0$, and score are as follows:

Scoring Parameters

This problem uses a Special Judge.

Thanks to @035966_L3 for providing the Special Judge.

If your output format is wrong, or the numbers you output are not in $1 \sim N$, or there are other errors, then you are doomed.

If your output format is correct, suppose the minimum angle you obtain is $Z$. Then your score is:

• If $Z \ge Z_0$, you will get full score.
• If $Z < Z_0$, let the score of this test case be $S$, then you will get $S \times \frac{f(Z/180)}{f(Z_0/180)}$.

Define the function $f(\alpha)\ (0 \le \alpha \le 1)$ as:

Evaluation Library

We additionally provide an evaluation library (in the file aerobatics.h), which you can use to compute the angle (in degrees) formed by three points.

The calling formats are:

• double GetAngle(int xb,int yb,int xa,int ya,int xc,int yc) or double GetAngle(int xb,int yb,int xc,int yc,int xa,int ya)
  • This function computes $\angle ABC$, with sufficiently small error.
  • Please ensure the order is correct.
  • $(xa, ya)$ is point $A$.
  • $(xb, yb)$ is point $B$.
  • $(xc, yc)$ is point $C$.
  • If $(xa, ya) = (xb, yb)$ or $(xa, ya) = (xc, yc)$, then, heh, hehehe.

Additional File Description

1. Name: aerobatics-dist.zip in the attachments below.
   • in & out: sample input and output.
   • aerobatics.h: evaluation library.
2. Name: aerobatics-data.zip in the attachments below:
   • in: input data.

Notes

Translated from The 20th Japanese Olympiad in Informatics Spring Training Camp Day1 A Aerobatics (曲芸飛行) English version.

Translated by ChatGPT 5