Wesley's Anger Contest Reject 4 - GPS

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

Mesley is trying to find his location! He is somewhere at an integer location on the 2-D plane, but he does not know where. He knows the location of 3 distinct, non-collinear satellites, with the i^\text{th} satellite at location (x_i, y_i) and his distance squared d_i^2 to them. Can you help him find his location (x_t, y_t)?


For this problem, you will be required to pass all the samples in order to receive any points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

1 \le x_i, y_i \le 1\,000\,000\,000
1 \le x_t, y_t \le 1\,000\,000\,000
None of the three satellites or Mesley's locations are collinear.

Subtask 1 [14%]

1 \le x_i, y_i \le 1\,000
1 \le x_t, y_t \le 1\,000

Subtask 2 [16%]

1 \le x_i, y_i \le 1\,000\,000
1 \le x_t, y_t \le 1\,000\,000

Subtask 3 [70%]

No additional constraints.

Input Specification

The input consists of 3 lines. Each line contains 3 integers, x_i, y_i, d_i^2, indicating the location of the i^\text{th} satellite and Mesley's distance squared to that satellite.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output two space-separated integers (x_t, y_t) representing Mesley's location.

Sample Input

1 1 1
2 1 2
3 5 13

Sample Output

1 2


There are no comments at the moment.