11.3. Даешь квадрат (5)

Ломаная без самопересечений и самокасаний разделяет четырехугольник на две части, которые не лежат одна внутри другой. Каждая часть представляет собой многоугольник и задается отдельно путем перечисления координат вершин. Определить, является ли исходный четырехугольник квадратом.

Ввод из файла INPUT.TXT. В первой строке находится число M, задающее количество вершин первого многоугольника. Следующие M строк содержат пары целых чисел - координаты точек (X_i, Y_i). Если соединить точки в данном порядке, а также первую и последнюю точки, то получится первый многоугольник. Далее аналогично указываются число N – количество вершин второго многоугольника и N строк с координатами его вершин. Таким образом, тест занимает M + N + 2 строк. Начальная вершина и направление обхода вершин каждого многоугольника могут быть произвольными.

Вывод в файл OUTPUT.TXT. Выводится единственная строка со значением Yes или No – является четырехугольник квадратом или нет.

Ограничения: 3 ≤ M, N ≤ 1000; -100 ≤ X_i, Y_i ≤ 100; время 1 с.

Примеры

Ввод 1 Ввод 2

6 8

0 0 0 0

0 1 0 6

1 1 5 5

1 2 5 0

2 2 3 0

2 0 4 1

4 1 1

0 2 2 0

1 2 4

1 1 1 1

0 1 2 0

3 0

4 1

Вывод 1 Вывод 2

Yes No

11.4. Стена (6)

Жил-был жадный Король. Он приказал своему главному Архитектору построить стену вокруг его замка. Король был таким жадным, что не послушал предложение Архитектора построить красивую кирпичную стену совершенной формы с изящными высокими башнями. Вместо этого он приказал построить стену вокруг всего замка, используя минимальное количество камня, но потребовал, чтобы стена не подходила к замку ближе некоторого расстояния. Если Король узнает, что Архитектор использовал больше ресурсов для постройки стены, чем было абсолютно необходимо для удовлетворения требований, Архитектор лишится головы. Более того, Архитектор должен представить проект стены, где указано точное количество ресурсов.

Ваша задача - помочь Архитектору сохранить голову, написав программу, определяющую минимальную длину стены, которую можно построить вокруг замка, удовлетворив требования Короля.

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

Ввод из файла INPUT.TXT. Первая строка содержит два целых числа N и L, разделённых пробелом: N - число углов в замке Короля, а L - минимальное число футов, на которое Король разрешил приблизить стену к замку.

Следующие N строк описывают координаты углов замка в порядке обхода по часовой стрелке. Каждая строка содержит два целых числа x_i и y_i, разделённых пробелом и представляющих собой координаты i-го угла в футах. Все углы имеют различные координаты, и стены замка не пересекаются иначе как в углах.

Ограничения: 3 ≤  N ≤ 1000, 1 ≤  L ≤ 1000, -10000 ≤  x_i, y_i ≤ 10000, время 2 с.

Вывод в файл OUTPUT.TXT. Выводится единственное число - минимальная длина стены в футах, которая может быть построена вокруг замка согласно требованиям Короля с точностью до фута.

Пример

Ввод

9 100

200 400

300 400

300 300

400 300

400 400

500 400

500 200

350 200

200 200

Вывод

1628

11.5. Клад (6)

Кладоискатели обнаружили люк в подземелье с сокровищами, закрытый неподъемной квадратной чугунной плитой. К счастью, плита имеет сквозную трещину, разделяющую ее на две части, которые не лежат полностью одна внутри другой. Трещина представляет собой ломаную без самопересечений и самокасаний. В распоряжении кладоискателей имеется лебедка. Мощности лебедки хватает на то, чтобы двигать в определенном направлении без вращения каждую из частей, не поднимая ее, но не всю плиту целиком. Требуется по форме трещины определить, могут ли кладоискатели освободить люк.

Ввод из файла INPUT.TXT. В первой строке находится число N, задающее количество вершин ломаной. Следующие N строк содержат пары целых чисел - координаты вершин (X_i, Y_i). Ломаная получается путем последовательного соединения точек в данном порядке. Направление обхода вершин ломаной может быть произвольным. Точки (X₁ , Y₁) и (X_N , Y_N) лежат на одной или разных сторонах квадрата, остальные точки ломаной – внутри квадрата.

Ограничения: 3 ≤ N ≤ 100; -100 ≤ X_i ≤ 100; -100 ≤ Y_i ≤ 100; время работы программы до 2 сек.

Вывод в файл OUTPUT.TXT. Выводится единственная строка со значением Yes или No – возможность либо невозможность разъединения квадрата путем перемещения его частей по плоскости без вращений.

Примеры

Ввод 1 Ввод 2

5 4

0 0 3 0

0 1 4 1

1 1 1 1

2 2 2 0

2 0

Вывод 1 Вывод 2

Yes No

Подсказка. Если разъединение существует, то его можно добиться перемещением какой-либо плиты в направлении одной из звеньев ломаной разреза.

11.6. Треугольники (6)

Роман достаточно давно занимается в математическом кружке, поэтому он уже успел узнать не только правила выполнения простейших операций, но и о таком достаточно сложном понятии как симметрия. Для того чтобы получше изучить симметрию, Роман решил начать с наиболее простых геометрических фигур – треугольников. Он скоро понял, что осевой симметрией обладают так называемые равнобедренные треугольники. Напомним, что треугольник называется равнобедренным, если его площадь положительна, и у него есть хотя бы две равные стороны.

Недавно Роман, зайдя в класс, увидел, что на доске нарисовано n точек. Разумеется, он сразу задумался, сколько существует троек из этих точек, которые являются вершинами равнобедренных треугольников.

Требуется написать программу, решающую указанную задачу.

Ввод из файла INPUT.TXT. В первой строке целое число n (3 ≤ n ≤ 1500). Каждая из последующих строк содержит по два разделенных пробелом целых числа – x_i и y_i , определяющих координаты i-ой точки. Все координаты точек не превосходят 10⁹ по абсолютной величине. Среди заданных точек нет совпадающих.

Вывод в файл OUTPUT.TXT. В единственной строке необходимо вывести ответ.

Примеры

Ввод 1 Ввод 2

3 4

0 0 0 0

2 2 1 1

-2 2 1 0

0 1

Вывод 1 Вывод 2

1 4

Подсказка. Составим массив с длинами всех расстояний между точками. Для каждого элемента массива будем сохранять номера начальной и конечной точек. Таким образом, каждое ребро между двумя точками войдет в массив дважды. Для каждого ребра рассчитаем дополнительно угол наклона - против часовой стрелки от положительного направления оси X (значение от 0 до 2π).

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

Организуем просмотр отсортированного списка ребер. Два ребра могут быть сторонами очередного равнобедренного треугольника при выполнении следующих условий:

• ребра выходят из одной и той же вершины;

• ребра имеют равную длину;

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

Если некоторый треугольник равносторонний, то он будет посчитан 3 раза по каждой из своих вершин. Проще всего учитывать в процессе перебора количество равносторонних треугольников, чтобы в конце сделать необходимую поправку.

11.7. Гомотетия (6)

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

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

• OY = |k|OX;

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

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

Ввод из файла INPUT.TXT. В первой строке входного файла содержится целое число n (3 ≤ n ≤ 1000) – количество вершин в каждом многоугольнике. В следующих n строках – по два целых числа x и y (-10⁶ ≤ x, y ≤ 10⁶) – координаты вершин первого многоугольника в порядке обхода против часовой стрелки. В следующих n строках – по два целых числа x и y (-10⁶ ≤ x,y ≤ 10⁶) – координаты вершин второго многоугольника в порядке обхода против часовой стрелки.

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

Примеры

Ввод 1 Ввод 2

3 3

-1 1 -1 1

1 1 1 1

1 5 1 5

1 9 1 1

-3 1 0 0

1 1 1 0

Вывод 1 Вывод 2

YES NO

1 0 1 0 2 0

11.8. Пересечение отрезков (5)

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

Ввод из файла INPUT.TXT. В первой строке содержатся координаты первого конца первого отрезка, во второй - второго конца первого отрезка, в третьей и четвёртой - координаты концов второго отрезка.

Вывод в файл OUTPUT.TXT. Выводится слово "Yes", если общая точка есть, или слово "No" - в противном случае.

Ограничения: координаты целые и по модулю не превосходят 10 000, время 1 с.

Примеры

Ввод 1 Ввод 2

0 0 0 0

1 0 1 0

1 0 2 0

1 1 3 0

Вывод 1 Вывод 2

Yes No

11.9. Выпуклая оболочка (6)

Найти выпуклую оболочку множества точек методом Грэхема.

Ввод из файла INPUT.TXT. В первой строке находится число N, задающее количество точек. Следующие N строк содержат пары целых чисел - координаты точек (X_i, Y_i). в порядке обхода против часовой стрелки, начиная от самой левой из самых нижних вершин.

Вывод в файл OUTPUT.TXT. В первой строке выводится M – количество вершин минимальной оболочки. Следующие N строк содержат пары целых чисел - координаты вершин (X_i, Y_i) в порядке обхода против часовой стрелки, начиная от самой левой из самых нижних вершин.

Ограничения: координаты целые и по модулю не превосходят 10000, время 1 с.

Примеры

Ввод

6

0 0

2 2

2 0

0 2

1 1

1 0

Вывод

4

0 0

2 0

2 2

0 2

11.10. Газон (6)

Фермер Иван с юности следит за своим газоном. Газон можно считать плоскостью, на которой в каждой точке с целыми координатами растет один пучок травы. В одно из воскресений Иван воспользовался газонокосилкой и постриг некоторый прямоугольный участок газона. Стороны этого участка параллельны осям координат, а две противоположные вершины расположены в точках (x₁, y₁) и (x₂, y₂). Следует отметить, что пучки травы, находящиеся на границе этого прямоугольника, также были пострижены. Довольный результатом Иван купил и установил на газоне дождевальную установку. Она была размещена в точке с координатами (x₃, y₃) и имела радиус действия струи r. Таким образом, установка начала поливать все пучки, расстояние от которых до точки (x₃, y₃) не превышало r. Все было хорошо, но Ивана заинтересовал следующий вопрос: сколько пучков травы оказалось и пострижено, и полито в это воскресенье? Требуется написать программу, которая позволит дать ответ на вопрос Ивана.

Ввод из файла INPUT.TXT. В первой строке содержатся четыре целых числа x₁, y₁, x₂, y₂ (−100 000 ≤ x₁ < x₂ ≤ 100 000; −100 000 ≤ y₁ < y₂ ≤ 100 000). Во второй строке входного файла содержатся три целых числа x₃, y₃, r (−100 000 ≤ x₃, y₃ ≤ 100 000; 1 ≤ r ≤ 100 000)

Вывод в файл OUTPUT.TXT. Вывести одно число - количество пучков травы, которые были и пострижены, и политы.

Пример

Ввод

0 0 5 4

4 0 3

Вывод

14

Иллюстрация к примеру

11.11. За решеткой (6)

Два бегемота, Вася и Эдик, живут в зоопарке. Каждый живет в отдельной прямоугольной клетке, три стены которой каменные, а четвертая образована решеткой. Через решетки бегемоты видят друг друга. Однажды ночью обоих мучила бессонница, и Вася предложил сыграть в морской бой, чтобы скоротать время. Чтобы сообщать о своем ходе как можно тише (ночь все-таки, все остальные звери спят), Эдик предложил найти такие положения около решеток, расстояние между которыми минимально.

Ввод из файла INPUT.TXT. В единственной строке задаются через пробел восемь чисел: сначала описание первой решетки, затем второй. Каждая решетка задается координатами концов (x₁, y₁, x₂, y₂). Все числа целые, по модулю не больше 10000.

Вывод в файл OUTPUT.TXT. В единственной строке вывести минимальное расстояние, которое может быть между Васей и Эдиком, если каждый будет стоять около своей решетки. Расстояние должно быть выведено с тремя знаками после запятой.

Пример

Ввод

0 1 0 5 1 -1 1 0

Вывод

1.414

11.12. А у нас в квартире газ (6)

В некотором районе проводится всеобщая газификация. Для этого прежде всего нужно построить газораспределительную станцию. Она может располагаться только на участке магистрального газопровода, соединяющего по прямой пункты A и B. На карте района известны координаты этих пунктов (u₁, v₁) и (u₂, v₂) соответственно. От станции протягиваются отдельные прямолинейные трубы к N (N ≤ 100) населенным пунктам c координатами (x_i, y_i) (-100 ≤ x_i, y_i ≤ 100). Известно, что затраты на проведение газовой трубы равны квадрату длины трубы. Требуется указать такие координаты газораспределительной станции, чтобы общие затраты на трубы были минимальны.

Ввод из файла INPUT.TXT. В первой строке задается значения N. Во второй строке указываются через пробел u₁, v₁, u₂, v₂. В следующих N строках задаются через пробел координаты x_i, y_i населенных пунктов.

Вывод в файл OUTPUT.TXT. Вывести с семью знаками после запятой: в первой строке координаты станции, во второй строке минимальную стоимость труб.

Пример

Ввод

2

0 0 4 4

1 1

3 3

Вывод

2.0000000 2.0000000

4.0000000

11.13. Длина линии (6)

Имеется круг радиуса R с центром в начале координат. Заданы две точки (X₁,Y₁) и (X₂,Y₂). Требуется найти минимальную длину линии, соединяющей эти точки, но не пересекающей внутренность круга.

Ввод из файла INPUT.TXT. В первой строке находится целое число N – количество блоков входных данных. Далее следуют N строк, каждая из которых содержит пять вещественных чисел через пробел - X₁, Y₁, X_{2 var container = document.getElementById('nativeroll_video_cont'); if (container) { var parent = container.parentElement; if (parent) { const wrapper = document.createElement('div'); wrapper.classList.add('js-teasers-wrapper'); parent.insertBefore(wrapper, container.nextSibling); } }}