Hide

Problem F
Tricky Triangulation

/problems/trickytriangulation/file/statement/en/img-0001.png

Amy is trying to find a stronghold by using Eyes of Ender. When thrown, Eyes of Ender fly in the direction of the closest stronghold. However, since Eyes of Ender have a chance of breaking when thrown, Amy wants to limit the number of throws she makes. So, she attempts to locate the stronghold by only using 2 throws.

In Minecraft, locations are represented by block coordinates, $(x, y)$, where both $x$ and $y$ are integer values. Amy is able to record the block coordinates at which she makes her throws, $(x_1, y_1)$ and $(x_2, y_2)$, where $- 10^{9} \leq x_1,y_1,x_2,y_2 \leq 10^{9}$. However, she is unable to accurately locate where the Eyes of Ender land after thrown. Instead, she walks in the direction of the thrown Eyes of Ender for some distance, and records the block coordinates at which she stops, $(x_1^\prime , y_1^\prime )$ and $(x_2^\prime , y_2^\prime )$, where $- 10^{9} \leq x_1^\prime , y_1^\prime , x_2^\prime , y_2^\prime \leq 10^{9}$. It is possible that Amy overshot the location of the stronghold as she walks in the direction of the thrown Eyes of Ender, but she may still be able to find the stronghold in this case.

Given these coordinates, write a program to determine if there is a unique stronghold location determined by the two throws, and if so, what the coordinates of the stronghold are.

Input

The only line of input contains the integers $x_1, y_1, x_1^\prime , y_1^\prime , x_2, y_2, x_2^\prime , y_2^\prime $, each separated by a space ($- 10^{9} \leq x_1, y_1, x_1^\prime , y_1^\prime , x_2, y_2, x_2^\prime , y_2^\prime \leq 10^{9}$). It is guaranteed that the start and end locations for each throw are distinct, and she never starts a throw at the same coordinates as the stronghold.

Output

If there is exactly one possible location for a stronghold based on the two throws, print the block coordinates $(x_ a, y_ a)$ for this location, rounded down to the nearest integer ($- 10^{9} \leq x_ a, y_ a \leq 10^{9}$). Otherwise, print $-1$.

Sample Input 1 Sample Output 1
395 -188 420 -150 395 921 400 850
465 -81
Sample Input 2 Sample Output 2
395 -188 420 -150 400 850 395 921
-1
Sample Input 3 Sample Output 3
395 -188 420 -150 395 -188 420 -150
-1
CPU Time limit 1 second
Memory limit 1024 MB
Author
Bill Liu
Source CodeSprint LA 2021
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in