Темы --> Информатика --> Алгоритмы --> Вычислительная геометрия
    Градиентный спуск(1 задач)
    Элементарная геометрия(144 задач)
    Многоугольники. Выпуклые оболочки(38 задач)
    Клеточная геометрия(8 задач)
    Квадродерево(3 задач)
---> 2 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников --> Окружная олимпиада --> 2008 (четвертый интернет-этап)
    запад(3 задач)
    восток(3 задач)
Страница: 1 Отображать по:
#1151
Гомотетия
  

Гомотетией с центром O и коэффициентом k 0 называют преобразование плоскости, при котором точка O переходит сама в себя, а любая точка X 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».

Примеры
Входные данные
3
-1 1
1 1
1 5
1 9
-3 1
1 1
Выходные данные
YES
1.0 1.0 2.0
Входные данные
3
-1 1
1 1
1 5
1 1
0 0
1 0
Выходные данные
NO
#1154
Скользящая симметрия
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Движением плоскости называют такое преобразование плоскости, которое сохраняет попарные расстояния между точками, то есть если A1 и B1 – образы некоторых точек A и B при движении, то |A1B1| = |AB|.

Одной из разновидностей движения плоскости является скользящая симметрия. Скользящей симметрией называют композицию симметрии относительно некоторой прямой l и переноса на вектор, параллельный l (этот вектор может быть нулевым). На рисунке показан пример применения скользящей симметрии к отрезку.

 

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

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

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

В первой строке входного файла находятся четыре целых числа – координаты двух различных точек A и В. Во второй строке также находятся четыре целых числа – координаты двух различных точек A1 и В1. Гарантируется, что |A1B1| = |AB|. Все числа во входном файле по модулю не превышают 1000. Числа в строках разделены пробелом.

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

Выведите в выходной файл описание искомой скользящей симметрии, которое представляется в следующем виде.

В первой строке должны выводиться координаты двух различных точек, лежащих на прямой l, относительно которой выполняется симметрия, а во второй – координаты вектора, параллельного этой прямой, на который осуществляется перенос. Вещественные числа должны быть представлены не менее чем с 6 знаками после десятичной точки.

Примеры
Входные данные
1 1 3 2
-1 1 -3 2
Выходные данные
0.000000 0.000000 0.000000 1.000000
0.000000 0.000000
Входные данные
1 1 3 1
3 -1 5 -1
Выходные данные
0.000000 0.000000 1.000000 0.000000
2.000000 0.000000
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест