Submit Best Submissions All Submissions

187. Centroid of Point Masses

Problem Statement:
The "centroid" of a region in two dimensions can be thought of as the point at which the region would balance on the end of a pencil. Computing this would require a bit more effort than we have in mind for this problem, so we restrict our attention to finding the centroid of a collection of point masses.

In this case, we could view the plane as being a thin, massless sheet with a few heavy points on it and ask where the plane would balance. To be more rigorous, we present a mathematical definition of the centroid for this case.

Given the coordinates (xi, yi) of a set of n points and the mass mi at each point, we define the x-moment of that set of points relative to a given point (a, b) as follows (note the x-moment is defined in terms of y differences, but we will need both moments, so it doesn't really matter which way this is done for this particular problem)

Similarly, the y-moment is defined as

The centroid of that set of points is defined to be the point (a, b) for which both moments are zero.

Input Format:
Input will be sets of points. Each set will be specified by the number of points n in the set followed by n lines of three numbers representing xi, yi, and mi values for i = 1 to n. All these numbers will be integers from 1 to 5000. That is, n will be from 1 to 5000 and all the coordinates and masses will also be from 1 to 5000, just to make input easier. End of input will be marked by a negative value of n. There will be extra white space in input so that judges can read the input cases easily. Do not assume any particular number of spaces before, between, or after the input values, and do not assume a particular number of blank lines between cases.

Output Format:
Print the coordinates of the centroid. Follow the format exactly: "Case", a space, the case number, a colon and one space, and the values of a and b rounded to two decimal places separated by one space. Input will be constructed so that rounding will not cause problems for values that are sufficiently close to correct. Do not print any trailing spaces.

Sample Input:
3 1 1 10 22 1 10 1 31 10 3 10 10 100 20 20 50 10 40 30 -4

Sample Output:
Case 1: 8.00 11.00 Case 2: 12.78 17.78

Added by: feras_kassar
Added at: 2014-07-26 09:00:04 UTC
Time Limit: 3 seconds
Partial score: No