I use the fomula to find average of n values X[i], i=1...n  if I know the average of (n-1) values X[i], i=1...(n-1):

AVE(X, n) = ((n-1)AVE(X, n-1) + X[n]) / n

This doesn't help.

1.sort(X[]).
2.add (X[i+1]-X[i])*i*(n-i).

Brilliant idea. I've got it.
Thanks.

i've got smth similar but i don't understand how to sort it... pls help

I don't have any ideea... how did you solve this problem? I've got TLE ... I use brute force.. LOL

Doesn't work with 4 10 10 10 20 20 10 20 20!

1.sort(X[]).
2.add (X[i+1]-X[i])*i*(n-i).

Edited by author 07.04.2011 01:25

how do you sort it, what is min and what is max after sort... i've got WA for 3 20 20 30 30 50 10

must work!
segment[X[i],X[i+1]] is passed by all pairs from [1..i]*[i+1,..n] or i*(n-i) times
where i in[1..n-1]

i still don't get it... pls send me your source at lerh_91@live.com

Because for a given point i we can only go to another point vertically or horizontally and that's a great hint.

Consider an input file that contains 7 points (index from 1 to n), and now we have sorted them by x[] in ascending order.

Now let's consider the segment between point 5 and point 6, denoted by S(S=x[6]-x[5], remember that we have sorted the points by x[]). Now if we want to go from point 2 to point 6, we must pass through S, and likewise, if we want to go from point 1,2,3,4,5 to point 6,7, we have to pass through S. Inversely, from point 6,7 to point 1,2,3,4,5, we must pass through S. Actually, for a given segment x[i+1]-x[i], we have to pass through this segment i*(n-i)*2 times, for there are i points before and including the ith point and (n-i) points after the ith point, and we have to go from left to right and from right to left. This analysis is also true for the y coordinate.

By this method we can get the total distance from every point to every other point.

Finally just divide the total distance by (n*(n-1)) to get the average distance because there are n points and each point has (n-1) road to the other points.

In conclusion, the solution would be :
for(i = 1 to n-1)
{
    ans += (x[i+1]-x[i]) * i * (n-i) * 2;
    ans += (y[i+1]-y[i]) * i * (n-i) * 2;
    // or ans += (x[i+1]-x[i] + y[i+1]-y[i]) * i * (n-1) * 2;
}
ans /= ( n*(n-1) )

Be careful about the data type of ans, int is not enough, use long long

thank

really good explanation