|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
C - Computing Near-Death Experience
Languages: C, C++, Java, Python, Kotlin, C#
Time & Memory limits: (details)
Due to Prof. Farnsworth's age, he was finally forced to move out into the Near-Death Star, an artificial satellite whose elderly inhabitants are connected to power-generating pods that keep the inhabitants' minds entertained in a virtual reality simulation. As his near-last wish, Prof. Farnsworth has chosen to ``live'' in a simulation of the farm he lived at when he was a child.
There he has plenty of space to do and invent whatever crazyness he wants, in fact, one of his latest inventions is the one he is the most proud of. It consists of a circle shooting machine that can shoot circles over a huge canvas. Well ok, it's not that big of a deal, but it is for him. In fact, it's really entertaining for him to try to cover all the $N$ holes randomly placed in the canvas every day in the morning using the minimum number of shots.
The machine can only shoot circles of a certain radius r over the canvas. Our professor wants something (an app, maybe) that can help him determine whether he succeded on his goal or not by telling him what is the minimum number $K$ of shots needed to cover all the holes.
Input
First line contains an integer $N$ and a real number $r$, ($1 \leq N \leq 20$, $1 \leq r \leq 2000$), the number of points and the radius respectively. Then follow $N$ lines, the $i-th$ of which has the real number coordinates $x_i$ and $y_i$ ($-1000 \leq x_i, y_i \leq 1000$) of a hole.
Output
One number $K$, the minimum number of shots needed to cover all the holes.
Sample test(s)
Input
6 2
0 0
2 1
2 -1
4 1
4 -1
6 0
Output
2