P7558 [JOISC 2021] Aerobatics (Day1)

**This is an output-only problem.** SPJ modified by wlzhouzhuan.

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: $$\min\limits_{i=2}^{n-1}\{\alpha_i\}$$

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 $N$ lines, each containing an integer $P_k$, representing the index of the $k$-th visited point.

#### 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: |Test case ID|$N$|$Z_0$|Score| |:-:|:-:|:-:|:-:| |$1$|$15$|$100$|$10$| |$2$|$200$|$143$|$15$| |$3$|$200$|$134$|$15$| |$4$|$1000$|$156$|$20$| |$5$|$1000$|$150$|$20$| |$6$|$1000$|$153$|$20$| #### Scoring Parameters **This problem uses a Special Judge.** Thanks to @[035966_L3](https://www.luogu.com.cn/user/365654) for providing the [Special Judge](https://www.luogu.com.cn/blog/12322655-4/p7558spj). 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: $$f(\alpha)=4\alpha^4+\alpha$$ #### 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](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/index.html) [Day1 A Aerobatics (曲芸飛行) English version](https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day1/aerobatics-en.pdf). Translated by ChatGPT 5