Problem E
European Trip

After winning Vietlott, a woman decided to go on a trip to Europe! Let’s refer to her as Ms. Mask.

Like other women, Ms. Mask really loves shopping and guess where her first stop is? Of course, it is London, a dream land for shopaholics. She has already discovered three greatest shopping centers in London: Westfield Stratford City, Piccadily Arcade and Fortnum & Mason. On the Cartesian plane, these three shopping centers can be depicted by three points.

Ms. Mask wants to rent a house to stay during the whole trip, so that the total distance from her house to those shopping centers are as small as possible. Help her find an optimal position for her house, assuming that she can put her house everywhere, even in Green Park or on Thames River!


The input consists of three lines, each line contains two integers $x$ and $y$ (between $0$ and $10^3$, inclusive) representing the coordinates of three shopping centers.

It is guaranteed that those three points are not collinear.


Write in one line two real numbers $x$ and $y$ representing the place where Ms. Mask should hire a house and stay.

Let $P$ be the total distance from your point to three points given in the input, and $J$ be the total distance from jury’s point. Your answer is considered correct iff $P$ differs from $J$ at most $10^{-4}$ in term of either absolute or relative value.

Sample Input 1 Sample Output 1
0 0
1 0
0 1
0.211324865 0.211324865
Sample Input 2 Sample Output 2
174 711
980 989
976 384
803.563974893 697.742533711

Please log in to submit a solution to this problem

Log in