There are N huge stones in the field, located in points P1,P2,…,PN (not necessarily different). Their weights are positive integer numbers W1,W2,…,WN.
You want to make a view on this field picturesque. To do this you should move these stones to the new points P′1,P′2,…,P′N, such that these points are lying at some circle. Let's define the difficulty to make this as a real number equal toN∑k=1dist(Pi,P′i)⋅Wi.
You want to find some circle with center in point (X0,Y0) and radius R , such that the difficulty to make all stones lying on this circle as minimal as possible. Points P′1,P′2,…,P′N will be chosen optimally for your circle, you should find only the circle.
Input format
- On the first line, you are given one integer number N (number of stones).
- On the next N lines you are given 3 integer numbers Xi,Yi,Wi,coordinates of point Pi and weight of i-th stone.
Output format
- Print 3 real numbers X0,Y0,R coordinates of the center of the optimal circle and its radius. This numbers should satisfy the conditions −106≤X0,Y0≤106 and 0≤R≤4⋅106.
Constraints
- N=50000 in all test cases except sample test
- Pi=(Xi,Yi),−106≤Xi,Yi≤106,1≤Wi≤106
Note: The input data contains only 50 percent of the original test data. The other data will be added after the contest and the submissions will be rejudged.
Verdict and scoring
If numbers X0,Y0,R don't satisfy the required conditions you will get a Wrong Answer verdict. For each of the valid output points P′1,P′2,…,P′N will be generated, such that difficulty as minimum as possible.
In the sample test, we can choose (X0,Y0)=(−1,2) and R=1.
In this case, most optimal points are: P′1=(−1,3), P′2≈(−0,2929,1,2929), P′3=(−2,2), P′4≈(−1.8944,1,5528). The minimal possible difficulty for this circle is ≈3,6503.
