0
$\begingroup$

my friend and I have a question regarding problem "Pesky Mosquitoes" ( https://open.kattis.com/problems/mosquitoes ) from Kattis OJ (online judge for competitive programming. This clearly is clearly a fairly simple geometry problem. See how many points lie inside a circle of a given diameter. Our idea is pretty straightforward. We take every pair of points and find the midpoint between those two points. We call that the center of our new circle, which will have the radius taken from dividing the previously given diameter by 2. Then, we just check how many points lie inside of it. However, we get a veredict of WA on the dataset of Kattis. What is wrong with that idea? Any help would be appreciated.

$\endgroup$
1
$\begingroup$

Consider an example where you have a bowl of diameter $2$ and three mosquitoes at the coordinates $(0,-1)$, $(0.5, 0.866)$, and $(-0.5, 0.866)$. If you put the center of the bowl exactly at $(0,0)$ you will just barely trap all three mosquitoes. But if you move the bowl more than a tiny distance in any direction—in particular, if you move the center of the bowl to any of the midpoints of the segments between any two mosquitoes—at least one mosquito will escape.

So maybe the algorithm isn't quite as simple as it looks.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.