Задача №111271. Фотооптимизация

На Международной олимпиаде по информатике некоторые участники, конечно же, получают удовольствие именно от решения предложенных задач, но большинство — от полученных в новой стране впечатлений. Впечатления принято запечатлевать на фотоаппарат. Участник T решил подойти к процессу съёмок с научной (по его мнению) точки зрения. Он находится на круглой обзорной площадке и желает заснять сразу два интересных объекта, местоположение каждого из которых на земле мы будем описывать с помощью отрезка. T выбирает точку для съёмок внутри этой площадки так, чтобы суммарная площадь двух треугольников, образованных концами соответствующих отрезков и выбранной точкой на обзорной площадке была как можно больше.

Помогите T с выбором такой точки. Возможность заснять сразу два объекта при этом анализировать не нужно, мы лишь действуем в рамках модели, сформулированной T. Если объекты загораживают друг друга, то этим также нужно пренебречь и считать площади независимо.

Входные данные

В первой строке входного файла находятся число T — количество тестов (1 ≤ T ≤ 105). Далее следуют описания тестов. В первой строке каждого описания содержится 4 числа x1, y1, x2, y2, характеризующие координаты концов первого отрезка. Во второй строке — x3, y3, x4, y4, описывающие второй отрезок. В третьей строке записаны три числа x0, y0, R — координаты центра круговой площадки и её радиус. Все числа целые, по модулю не превосходящие 1 000. Радиус положителен.

Гарантируется, что отрезки невырождены и не пересекаются с круговой площадкой. Также гарантируется, что они не имеют общих внутренних точек.

Выходные данные

Для каждого теста выведите координаты точки внутри круга, удовлетворяющей условию задачи. Если таких точек несколько, то выведите любую из них. Координаты следует выводить с как можно бóльшим числом знаков после десятичной точки. Соответствующая сумма площадей должна отличаться от правильного ответа по абсолютной или относительной величине не больше чем на 10 - 6.

Примеры тестов

Входные данные
1
0 0 1 0
0 0 -1 0
0 2 1
Выходные данные
0.0000000000 3.0000000000

Сдать: для сдачи задач необходимо войти в систему