Practice on Toph

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


By Arcturus · Limits 1s, 512 MB

The Merry-Go-Round is an amusement ride, popular in rural Bangladesh. Today is your birthday, and to treat your $N$ friends, you have decided to take them to an amusement park to enjoy the Merry-Go-Round ride. But this ride is special. Why so? Because it has infinitely many seats and one seat can be shared among infinitely many people.

A Merry-Go-Round cam be considered as a circle, balanced on a pivot at the center, that looks like this:

Consider the seats as individual points on the circle boundary/perimeter. When no seat is occupied, the center of the gravity remains at the pivot. So the system is perfectly horizontally balanced at the pivot. But, if some seats are occupied by one or more people, the center of gravity may be displaced from the center of the circle.

Another specialty of this Merry-Go-Round is its cost of riding. This cost is defined as the distance from the center of the circle to the displaced center of gravity. This distance is calculated as Pythagorean distance between two points i.e. $\sqrt{(x_0 - x_1)^2 + (y_0 - y_1)^2}$.

You are a genius and found out that if you can make your friends take seats in some particular ways, the cost could be reduced. Now you are given the weights of your $N$ friends, $w_1, w_2, \dots, w_N$ (not necessarily all equal), and the radius of the circle $R$. Find out the minimum cost you need to pay for the ride.

N.B.: You should ignore the weight of the circle.


The first line contains a single integer $T (1 \leq T \leq 10^4)$ - the number of test cases.

The first line of each test case contains 2 space-separated integer $N (1\leq N \leq 10^5)$ and $R (0 \leq R \leq 10^9)$ - the number of friends and the radius of the circle.

The second line of each test case contains $N$ space-separated integers $w_i (1 \leq w_i \leq 10^9)$.

It is guaranteed that the sum of $N$ over all test cases does not exceed $10^6$.


For each test case, print the minimum cost you need to pay in separate lines. An absolute precision error of less than $10^{-6}$ will be ignored.


2 6
5 10
4 20
12 12 12 12




    57% Solution Ratio

    BigBagEarliest, 2M ago

    YouKnowWhoFastest, 0.1s

    Muhimin_OsimLightest, 262 kB

    YouKnowWhoShortest, 465B


    Login to submit


    Case 1: sum of the rest < Biggest We are putting all the objects in two points in a single line...

    Related Contests