Задача №111281. Фотооптимизация
На Международной олимпиаде по информатике некоторые участники, конечно же, получают удовольствие именно от решения предложенных задач, но большинство — от полученных в новой стране впечатлений. Впечатления принято запечатлевать на фотоаппарат. Участник T решил подойти к процессу съёмок с научной (по его мнению) точки зрения. Он желает заснять сразу два интересных объекта, местоположение каждого из которых на земле мы будем описывать с помощью отрезка. T выбирает точку для съёмок так, чтобы площадь двух треугольников, образованных концами соответствующих отрезков и выбранной точкой была одинаковой. Треугольники при этом должны быть невырожденными.
Помогите T с выбором такой точки. Возможность заснять сразу два объекта при этом анализировать не нужно, мы лишь действуем в рамках модели, сформулированной T. Задача упрощается тем, что каждый из отрезков, описывающих объекты, оказался параллельным одной из осей координат (возможно, каждый своей).
В первой строке входного файла находятся 4 целых числа x1, y1, x2, y2, характеризующие координаты концов первого отрезка. Во второй строке — x3, y3, x4, y4, описывающие второй отрезок. Все координаты по модулю не превосходят 1000. Каждый отрезок параллелен одной из осей координат. То есть гарантируется, что у каждого отрезка или координаты x его концов или координаты y концов совпадают. Также гарантируется, что отрезки невырождены, и что они не имеют общих внутренних точек и могут касаться только своими концами.
Если точку, удовлетворяющую условию задачи, и координаты которой по абсолютной величине не превосходят 5000 найти можно, то в первой строке выведите слово «YES». В этом случае во второй строке выведите координаты найденной точки. Если таких точек несколько, то выведите любую из них. Координаты могут оказаться вещественными, и их следует выводить с как можно бóльшим числом знаков после десятичной точки. Разница соответствующих площадей должна быть не больше 10 - 3. Площадь каждого треугольника должна быть не меньше 0.1.
Если искомую точку найти невозможно, или координаты любой такой точки по модулю превышают 5000, то выведите только слово «NO».
0 0 0 4
5 2 5 3
YES
1.00000000000000 0.0000000000000000
1 0 3 0
1 0 1 1
YES
3.00000000000 1.000000000000000