astronomer (BOI contest)
Time limit: 5 seconds | Memory limit: 1024 MB | Task type: batch
Algorithms: geometry, ternary search, sorting, optimization

# Astronomer
Problem ID: astronomer

The astronomer has a passion for stargazing. In particular, he gets immense pleasure out of gazing at $k$ stars simultaneously through his telescope. Building a telescope with radius $r$ costs $t \cdot r$ kroner. A newly built telescope will point exactly at the origin $(0, 0)$. Moving it to point somewhere else also takes effort; shifting the telescope a distance of $d$ units incurs a cost of $s \cdot d$ kroner. The astronomer can observe all stars at distance at most $r$ from where the telescope points.

How much does it cost to build and move a telescope that allows $k$ stars to be observed at once?

All coordinates and distances are given in the Euclidean plane.

## Example

Here is an example with $n = 3$ stars at positions $(0, 0)$, $(2, 0)$, and $(3, 1)$. The shaded area shows a telescope of radius 1 pointing at $(1, 0)$ covering two stars; this costs $s + t$ kroner and is an optimal solution to sample input 3. The image also shows optimal solutions to sample inputs 1, 2, and 4.

![Example image](_page_0_Picture_6.jpeg)

![Tycho Brahe](_page_0_Figure_7.jpeg)

## Input

The first line consists of four integers: the number $k$ of stars the astronomer wants to observe, the number $n$ of stars in tonight's sky, the shifting cost $s$, and the telescope building cost $t$. Then follow $n$ lines, where the $i$th line contains the integer coordinates $x_i$ and $y_i$ of the $i$th star.

## Output

A single real number: the minimum number of kroner that the astronomer needs to spend.

## Constraints and Scoring

You can assume:

1. $1 \le k \le n \le 700$.
2. $x_i, y_i \in \{-10^9, \dots, 10^9\}$ for all $i \in \{1, \dots, n\}$.
3. $s, t \in \{0, \dots, 10^9\}$.
4. Your output is accepted if it is within a relative or absolute tolerance of $\epsilon = 10^{-6}$ of the correct answer.

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.

| Group | Points | Constraints |
|---|---|---|
| 1 | 8 | $t \le s$ |
| 2 | 9 | $n \le 50$ and $s = 0$ |
| 3 | 18 | $s = 0$ |
| 4 | 13 | $n \le 50$ |
| 5 | 14 | $n \le 350$ |
| 6 | 15 | $\epsilon = 1/10$ |
| 7 | 23 | No further constraints |

| Sample Input 1 | Sample Output 1 |
|---|---|
| `2 3 1000 500`<br>`0 0`<br>`2 0`<br>`3 1` | `1000.0` |

| Sample Input 2 | Sample Output 2 |
|---|---|
| `2 3 500 3000`<br>`0 0`<br>`2 0`<br>`3 1` | `3387.277541898787` |

| Sample Input 3 | Sample Output 3 |
|---|---|
| `2 3 250 750`<br>`0 0`<br>`2 0`<br>`3 1` | `1000.0` |

| Sample Input 4 | Sample Output 4 |
|---|---|
| `2 3 0 500`<br>`0 0`<br>`2 0`<br>`3 1` | `353.5533905932738` |

| Sample Input 5 | Sample Output 5 |
|---|---|
| `3 4 0 10`<br>`0 0`<br>`10 0`<br>`5 10`<br>`5 5` | `50.0` |

Starter code:

Grader code:

Setup script:

Evaluation script: