Practice on Toph

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

Walking Down The Road

Limits: 1s, 256 MB

There is an M meter long road with the leftmost point of the road being the 0 meter point and the right most point being the M meter point. N people are standing at different points on the road. Akina is a great problem solver. He likes to solve problems that are related to real life. Akina is thinking if the N peoples wanted to meet at certain point and they will just walk straight to that point from their position. If X is point where they can meet such that the summation of the distances each has to walk is minimum is called “Fuchka” point. Suppose a point can contain infinitely many people. You are given a similar problem. Suppose you have to say a random point between 0 to M. What is the probability of the random point being the “Fuchka” point?


First line will contain an integer T (1 ≤ T ≤ 5), the number of test case. Then for each case There will be two lines. First line will contain two integers N and M; (1 < N ≤ 100000) and (N ≤ M ≤ 2000000) and N is even. The next line will contain N number of integers the value of which will be between 0 to M inclusively. These points are the position of the people. No two points will be same.


For each case output a real number, the probability of the point being Fuchka point in a line.Error less then .000001 will be acceptable.


4 4
1 2 3 4
2 6
0 6


Login to submit