問題一覧 > 通常問題

No.1121 Social Distancing in Cinema

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 45
作問者 : e869120 / テスター : Thistle
お気に入りにしたユーザー ProblemId : 4640 / 自分の提出
問題文最終更新日: 2020-07-22 21:35:14
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 258 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。