Олимпиада (всеросийская заочная). Задача №2. << На главную или назад  

Задача 2.Гомотетия

Имя входного файла:
homoteth.in

Имя выходного файла:
homoteth.out

Максимальное время работы на одном тесте:
2 секунды

Максимальный объем используемой памяти:
64 мегабайта

Максимальная оценка
100 баллов

Гомотетией с центром O и коэффициентом k 1 0 называют преобразование плоскости, при котором точка O переходит сама в себя, а любая точка X 1 O – в такую точку Y, что:

§ Y лежит на прямой OX;

§ OY = |k|OX;

§ при k >0 Y лежит на луче OX, при k <0 Y лежит на продолжении луча OX за точку O.

Требуется написать программу, которая по координатам вершин двух различных простых N-угольников определяет, существует ли гомотетия, переводящая первый многоугольник во второй и, если существует, вычисляетее центр и коэффициент.

Формат входных данных

В первой строке входного файла содержится целое число n (3 ≤ n ≤ 1000) – количество вершин в каждом многоугольнике

В следующих n строках – по два целых числа x и y (-106 ≤ x,y ≤ 106) – координаты вершин первого многоугольника в порядке обхода против часовой стрелки.

В следующих n строках – по два целых числа x и y (-106 ≤ x,y ≤ 106) – координаты вершин второго многоугольника в порядке обхода против часовой стрелки.

Формат выходных данных

Если существует гомотетия, которая переводит первый многоугольник во второй, то необходимо вывести в первой строке выходного файла слово «YES», а во второй строке – три вещественных числа – координаты центра гомотетии и ее коэффициент, которые вычисляются с точностью не менее 10-5. Если искомой гомотетии не существует, необходимо вывести в выходной файл слово «NO».

Примеры входных и выходных данных

homoteth.in

3

-1 1

1 1

1 5

1 9

-3 1

1 1
homoteth.out
YES

1.0 1.0 2.0

homoteth.in
3

-1 1

1 1

1 5

1 1

0 0

1 0
homoteth.out
NO