Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Expected Light

By shourov.sust · Limits 1s, 512 MB

Bob has a circular land of radius R. He has built a circular building of radius r (r < R) at the center of his land. Bob wants to place n light sources on his land outside the building. He wants to place them such that expected number of lights can be seen from a random point on the land outside the building is maximized. A light source can be seen from a point if line segment connecting the point and light source doesn’t intersect with the building. For simplicity, suppose the building has infinite height. Find maximum possible expected number of lights can be seen from a random point outside the building (of course in his land) if light sources are placed optimally.


The first line contains one integer $T$ ( $1\leqslant T \leqslant 10^5$ ) — the number of test cases. Each test case is represented by one line containing three integers $R$, $r$, and $n$ ($1\leqslant$ $R,r,n \leqslant 10^5$).


For each test case, print maximum expected number of lights rounded to three decimal places.


2 1 1
5 2 3



    100% Solution Ratio

    YouKnowWhoEarliest, 3M ago

    YouKnowWhoFastest, 0.1s

    YouKnowWhoLightest, 1.0 MB

    YouKnowWhoShortest, 578B


    Login to submit