Вычислительная геометрия (стр. 3 )

Ограничения: 3 ≤ N ≤ 100; -100 ≤ Xi ≤ 100; -100 ≤ Yi ≤ 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). Каждая из последующих строк содержит по два разделенных пробелом целых числа – xi и yi , определяющих координаты i-ой точки. Все координаты точек не превосходят 109 по абсолютной величине. Среди заданных точек нет совпадающих.

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

Вывод в файл 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. Выпуклая оболочка (7)

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

Ввод из файла INPUT. TXT. В первой строке находится число N (1 ≤ N ≤ 105) , задающее количество точек. Следующие N строк содержат пары целых чисел - координаты точек (Xi, Yi).

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

Ограничения: координаты целые и по модулю не превосходят 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)

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

Ввод из файла INPUT. TXT. В первой строке содержатся четыре целых числа x1, y1, x2, y2 (−100 000 ≤ x1 < x2 ≤ 100 000; −100 000 ≤ y1 < y2 ≤ 100 000). Во второй строке входного файла содержатся три целых числа x3, y3, r (−100 000 ≤ x3, y3 ≤ 100 000; 1 ≤ r ≤ 100 000)

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

Пример

Ввод

0 0 5 4

4 0 3

Вывод

14

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

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

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

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

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

Пример

Ввод

0 1 0 5 1 -1 1 0

Вывод

1.414

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

В некотором районе проводится всеобщая газификация. Для этого прежде всего нужно построить газораспределительную станцию. Она может располагаться только на участке магистрального газопровода, соединяющего по прямой пункты A и B. На карте района известны координаты этих пунктов (u1, v1) и (u2, v2) соответственно. От станции протягиваются отдельные прямолинейные трубы к N (N ≤ 100) населенным пунктам c координатами (xi, yi) (-100 ≤ xi, yi ≤ 100). Известно, что затраты на проведение газовой трубы равны квадрату длины трубы. Требуется указать такие координаты газораспределительной станции, чтобы общие затраты на трубы были минимальны.