CS
Problems Base course RU

Problem

A pick-up point

optimization gradient iterative points logistics

A delivery service is opening a pick-up point in a city. There are n known places orders come from: coordinates (xi, yi) in metres and the number of orders wi from each place. A courier carries each order separately, and for the estimate the path is taken as a straight line. Find the point p for which the total path

$$F(p) = \sum_{i=1}^{n} w_i \cdot \lvert p - a_i \rvert$$

is smallest. Here ai = (xi, yi), and |…| is the ordinary distance on the plane. The point can be placed anywhere, not necessarily at an intersection. One of the tests is the intersections of central Almaty from OpenStreetMap with made-up numbers of orders.

Input

The first line holds the number of places n (1 ≤ n ≤ 10,000). Each of the following n lines holds three integers xi, yi, wi (|xi|, |yi| ≤ 10⁶, 1 ≤ wi ≤ 10⁶). Places may repeat.

Output

Two numbers, the coordinates x and y of the pick-up point. If there are several suitable points, print any. The answer is accepted if F at your point exceeds the smallest possible value by a factor of at most 1 + 10⁻⁷.

Examples

Example 1

Input
4
0 0 1
400 0 1
400 300 1
0 300 1
Output
200.000000 150.000000

Example 2

Input
3
0 0 5
1000 0 2
0 1000 2
Output
0.000000 0.000000

Limits

Time · Python
4000 ms
Time · Go
1000 ms
Memory
256 MB
Judging
10 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

If the courier travelled not in straight lines but “in squares”, that is, if the sum of wi·|p − ai|² had to be made smallest, the answer would be the weighted centre of mass. Why does it not do here? Look at the second example: where should the point go if one place has more orders than all the others together?

2Hint 2

There is no formula for the answer, but F is a convex function, and it has a gradient everywhere except at the points ai themselves: −∇F(p) = Σ wi·(ai − p)/|ai − p|. Each place pulls the point towards itself with force wi, regardless of distance. You can descend. What step should you take?

3Hint 3

Set the gradient to zero and express p: you get p = Σ(wi/di)·ai / Σ(wi/di), where di = |ai − p|. The right-hand side depends on p: substitute again and again.

4The idea

This is Weiszfeld’s iteration, published in 1937 by the mathematician Endre Weiszfeld, who later took the name Andrew Vázsonyi and worked in operations research. The new point is the average of the places with weights wi/di. Written out, it is exactly a gradient descent step p ← p − η∇F(p) with step η = 1/Σ(wi/di): the step chooses itself, shorter when the point has come close to heavy places and the function bends sharply there. The value of F does not grow at any step, and if no step lands exactly on one of the places, the iterations converge to the minimum.

The trap is the places themselves. There is no gradient at them, and if the answer is one of the places, the iterations creep up to it ever more slowly, and landing exactly on it, they divide by zero. For a place aj there is an exact test: it is the answer when the others pull it with a total force no greater than its own weight, |Σi≠j wi·(ai − aj)/|ai − aj|| ≤ wj. In the second example the weight of the first place is 5, and the others pull it with a force of 2√2 ≈ 2.83: the point goes right onto it.

5Walkthrough

First merge identical places, adding up their weights: this makes the test for a place correct. Start from the centre of mass and take Weiszfeld steps while the point moves by more than 10⁻⁷ metres (a few dozen steps are enough on the tests). If at some step the point coincides with a place, check the test: if it holds, the answer is found; if not, move off the place by a millimetre in the direction the others pull it, and carry on. At the end check the test for the place nearest the final point: if it holds, print the place itself, since the iterations were only creeping up to it.

Compare with the centre of mass. On the intersections of central Almaty it loses to the minimum by only a few millionths: the cloud of points is almost symmetrical, and the two points are close. In the seventh test thirty distant suburbs pull the centre of mass towards themselves, and the loss is already about 0.3%: in a sum of squares a distant point weighs disproportionately much, while in a sum of distances it weighs exactly as many orders as it has.

5+Solution
6Complexity

O(n) per step, usually a few dozen steps; the test is another O(n).

7Common mistakes
  • The centre of mass. It minimises the sum of squared distances, not the sum of distances. In the second example it is at (2000/9, 2000/9), while the answer is at the heaviest place, (0, 0).
  • Repeated places. The test for a place is correct only if identical places are merged into one with the total weight: otherwise “other” points at the same position give a distance of zero.
  • A constant descent step. The function has a kink at every place, and descent with a constant step jumps around an answer that is a place without hitting it.
  • Starting at the centre of mass without a check. In the tenth test the centre of mass falls exactly on one of the places, and not the answer: the very first Weiszfeld step divides by zero.

Algorithms behind it

NUM~ Algorithm Gradient descent Finds the minimum of a function by steps against the gradient, in the direction of steepest descent. O(κ · log(1/ε)) steps 2 problems
The algorithms catalogue