Background

• Original problem: P5617 [MtOI2019]Invisible Boundary Line.

Appendix: Some information about this problem’s SPJ and testdata.

If there are issues such as precision hacks, broken testdata, or cases that beat the intended solution, please contact the problem setter.

Problem Description

There are $n$ circles with radius $r$, drawn on a paper ring of length $L$ whose ends are connected.

All circle centers are at the same height. You can think of drawing a number line on the paper and then rolling it up; the positions of the centers are described by points on this number line.

If you cannot understand how the circles are distributed on the ring, please refer to the sample explanation and subtasks.

You need to choose $k$ circles so that the area of the union of all chosen circles is maximized.

Note that you must output an exact selection scheme, not just the maximum union area.

Input Format

The first line contains four integers $n, k, r, L$, with meanings as described in the statement.

The second line contains $n$ integers. The $i$-th integer $p[i]$ describes the position of the $i$-th circle center on the paper ring (the coordinate on the number line).

For $2<i<n$, we have $p[i-1] < p[i]$.

Output Format

Output one line containing $k$ integers, representing the indices of the circles you selected. The SPJ will compute the union area.

You must ensure these indices are strictly increasing and within $[1,n]$. Otherwise, it is considered invalid and you will receive no score.

It is considered correct if the relative error compared to the standard answer does not exceed $10^{-9}$, and the absolute error does not exceed $0.1$.

By estimation, the answer will not exceed the order of magnitude $10^{12}$.

5 3 10 30
0 7 14 21 28 

2 3 5 

10 3 10 65
0 7 15 24 30 36 41 49 57 63 

3 6 9

30 10 50 169
0 7 14 21 28 35 42 45 51 55 61 65 68 75 79 83 87 94 97 105 113 118 126 133 140 147 151 156 163 167 

3 5 8 11 15 19 21 24 27 30 

Hint

Sample Explanation:

• Sample 1: The final union area is approximately $565.871835$.

The distribution of circles is shown in the figure. Here, $⊙A$ and $⊙A2$ are the same circle, and $⊙B$ and $⊙B2$ are the same circle.

This can be viewed as shifting to the right by $L = 30$ units. In fact, this is equivalent to making a full round on the paper ring and returning to the start.

Since they are the same circle, the area covered by the red part cannot be counted repeatedly. The maximum union area is the blue part.

• Sample 2: The final union area is approximately $942.477796$.

• Sample 3: The final union area is approximately $16817.058547$.

Constraints and Conventions:

The time limit is more than twice the running time of std.

For all testdata, $n \leq 10^5$, $10 \leq r \leq 2000$, $0 \leq p[i] < L \leq 10^8$, $4r < L$, $3 \leq k \leq n$.

All values in the table are upper bounds. Note that some lower-bound restrictions may help remove certain boundary cases.

Translated by ChatGPT 5