Farmer Jane owns farming land in a city where property boundaries are defined by trees. The city council has determined that in order to avoid conflicts among neighbors, it will guarantee that in every property in the city, it should be possible to go from every point in the property, to any other point, using a straight path without leaving its boundaries. As a property owner, Farmer Jane must install an irrigation system to keep the trees delimiting her property in great condition. She has decided to install a single water sprinkler in some place of her property to water all the trees, but she wants to minimize the costs of doing so. The cost of watering a single tree, is given by the square of the distance from the tree to the sprinkler, times the amount of water needed by the tree. This is, for a tree located in position (xi, yi) that needs wi units of water, and a sprinkler located in position (x, y), the cost of watering the tree is given by wi · ((xi − x)2 + (yi − y)2). ∑ is to find the minimum cost of installing the sprinkler. It is possible to install a sprinkler in a point (x, y) where x and y are real numbers. Also, it is possible to install the sprinkler in the same position of a tree and in the boundaries of the property. Input The input consists of several test cases. The first line of a test case contains a single integer N indicating the number of trees delimiting the property (3 ≤ N ≤ 100). Then follow N lines: line i contains exactly 3 blank-separated integers xi, yi, and wi, where (xi, yi) is the position of the i-th tree (0 ≤ xi ≤ 1000, 0≤yi ≤1000),andwi isthenumberofunitsofwaterneededbythei-thtree(1≤wi ≤10). Youmay assume that there are not two trees located in the same position, and that the area of the property is a non-empty convex polygon. Output For each test case, print a single line with a number indicating the minimum cost of installing the sprinkler in the property. The answer should be formatted and approximated to three decimal places. The floating point delimiter must be ‘.’ (i.e., the dot). The rounding applies towards the nearest neighbor unless both neighbors are equidistant, in which case the result is rounded up (e.g., 78.3712 is rounded to 78.371; 78.5766 is rounded to 78.577; 78.3745 is rounded to 78.375, etc.). Sample Input 4 102 542 143 706 3 215 251 533 The cost of watering N trees is given by Ni=1 wi · ((xi − x)2 + (yi − y)2). Given the number N of trees delimiting the property, and values xi, yi, wi for each tree, your task
2/2 Sample Output 148.308 34.889