Light It Up

AtCoder

IDabc255_b

Time2000ms

Memory256MB

Difficulty—

There are $N$ people numbered $1, 2, \dots, N$ in the $xy$\-plane. Person $i$ is at the coordinates $(X_i, Y_i)$. $K$ of these people, Persons $A_1, A_2, \dots, A_K$, will receive lights of the same strength. When a person at coordinates $(x, y)$ has a light of strength $R$, it lights up the interior of a circle of radius $R$ centered at $(x, y)$ (including the boundary). Find the minimum strength of the lights needed for every person to be lit by at least one light. ## Constraints * All values in input are integers. * $1 \le K < N \le 1000$ * $1 \le A_1 < A_2 < \dots < A_K \le N$ * $|X_i|,|Y_i| \le 10^5$ * $(X_i,Y_i) \neq (X_j,Y_j)$, if $i \neq j$. ## Input Input is given from Standard Input in the following format: $N$ $K$ $A_1$ $A_2$ $\dots$ $A_K$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_N$ $Y_N$ [samples]

Samples

Input #1

Output #1

2.23606797749978969

This input contains four people. Among them, Persons $2$ and $3$ will have lights.  
Every person will be lit by at least one light if $R \ge \sqrt{5} \approx 2.236068$.

Input #2

2 1
2
-100000 -100000
100000 100000

Output #2

282842.712474619009

Input #3

8 3
2 6 8
-17683 17993
93038 47074
58079 -57520
-41515 -89802
-72739 68805
24324 -73073
71049 72103
47863 19268

Output #3

130379.280458974768

API Response (JSON)

{
  "problem": {
    "name": "Light It Up",
    "description": {
      "content": "There are $N$ people numbered $1, 2, \\dots, N$ in the $xy$\\-plane. Person $i$ is at the coordinates $(X_i, Y_i)$.   $K$ of these people, Persons $A_1, A_2, \\dots, A_K$, will receive lights of the same",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc255_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ people numbered $1, 2, \\dots, N$ in the $xy$\\-plane. Person $i$ is at the coordinates $(X_i, Y_i)$.  \n$K$ of these people, Persons $A_1, A_2, \\dots, A_K$, will receive lights of the same...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments