No.1121 Social Distancing in Cinema
Problem Statement
Yuki Cinema has $N$ seats numbered $1, 2, 3, ..., N$, and the seat numbered $i$ is located at coordinates $(x_i, y_i)$.
Currently, the cinema is closed due to a novel virus. To reopen, a way of operating it while maintaining social distancing must be devised. Specifically, it is as follows.
- Choose $K$ seats out of the $N$ seats, and let people sit only in those seats.
- Even when people are sitting in all $K$ seats, the distance between any two people must be at least $10$. (A distance of exactly $10$ is also fine.)
Here, "distance" means Euclidean distance. That is, the distance $D$ from coordinates $(a, b)$ to coordinates $(c, d)$ is as follows. $$D = \sqrt{(a-c)^{2} + (b-d)^{2}}$$ Output $1$ way of choosing seats such that $\frac{N}{90} \leq K$. It can be proved that, under the given constraints, a way of choosing seats that satisfies the conditions always exists. (added at 21:32)
Input
$N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $X_3$ $Y_3$ ... $X_N$ $Y_N$
The input is given over $N+1$ lines.
Line $1$ contains an integer $N$.
Line $1+i$ $(1 \leq i \leq N)$ contains integers $X_i, Y_i$ separated by a space.
Output
Output in the following format. This output format means that the seats numbered $B_1, B_2, ..., B_K$ are chosen and people sit only in those seats.
$K$ $B_1$ $B_2$ $B_3$ ... $B_K$
Here, the output must satisfy the following conditions.
- All output values are integers
- $\frac{N}{90} \leq K$
- $1 \leq B_i \leq N$
- All $B_i$ are distinct. That is, $B_i \neq B_j$ $(i \neq j)$
- The distance between any two chosen seats is at least $10$.
Constraints
- $1 \leq N \leq 250 \ 000$
- $1 \leq X_i, Y_i \leq 500$
- $(X_i, Y_i) \neq (X_j, Y_j)$ $(i \neq j)$
- All inputs are integers
Sample
Sample 1
Input
4 1 1 1 9 9 1 9 9
Output
2 1 4
This is correct because at least $\frac{N}{90} = 0.044444...$ seats are chosen.
Also, the distance between seats $1$ and $4$ is $\sqrt{(1-9)^2+(1-9)^2} = 11.3137... \geq 10$, which satisfies the condition.
Sample 2
Input
9 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
Output
1 5
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
e869120