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

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

Создайте структуру Point и сохраните исходные данные в массиве структур Point.

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

Программа получает на вход набор точек на плоскости. Сначала задано количество точек n (2<n<101), затем идет последовательность из n строк, каждая из которых содержит два числа: координаты точки. Все исходные координаты – целые числа, не превосходящие 10³.

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

Необходимо вывести найденную площадь с точностью в 15 значащих цифр.

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

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

Программа получает на вход набор точек на плоскости. Сначала задано количество точек n (2<n<101), затем идет последовательность из n строк, каждая из которых содержит два числа: координаты точки. Все исходные координаты – целые числа, не превосходящие 10³.

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

Необходимо вывести  найденный периметр с точностью в 15 значащих цифр.

Выведите диаметр данного множества – максимальное расстояние между любыми двумя точками.

Создайте структуру Point и сохраните исходные данные в массиве структур Point.

Входные данные
Программа получает на вход набор точек на плоскости. Сначала задано количество точек n, затем идет последовательность из n строк, каждая из которых содержит два числа: координаты точки. Величина n не превосходит 100, все исходные координаты – целые числа, не превосходящие 10³.

Выходные данные
Необходимо вывести  диаметр данного множества с точностью в 15 значащих цифр.

Выведите координаты центра тяжести данного множества точек.

Создайте структуру Pointи сохраните исходные данные в массиве структур Point.

Входные данные
Программа получает на вход набор точек на плоскости. Сначала задано количество точек n, затем идет последовательность из n строк, каждая из которых содержит два числа: координаты точки. Величина n не превосходит 100, все исходные координаты – целые числа, не превосходящие 10³.

Выходные данные
Выведите  координаты центра тяжести данного множества точек. Ответ необходимо выводить с точностью в 15 значащих цифр.

Выведите координаты наиболее удаленной от начала координат точки.

Входные данные
Программа получает на вход набор точек на плоскости. Сначала задано количество точек n, затем идет последовательность из n строк, каждая из которых содержит два числа: координаты точки. Величина n не превосходит 100, все исходные координаты – целые числа, не превосходящие 10³
по абсолютной величине.

Выходные данные
Выведите  координаты точки, наиболее удаленной от начала координат.

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

Входные данные
В первой строке вводится N (3≤N≤1000) – число вершин многоугольника. В последующих N строках идут координаты (X_i, Y_i) вершин многоугольника в порядке обхода по часовой стрелке. X_i и Y_i – целые числа, по модулю не превосходящие 10⁶.

Выходные данные
Вывести одно число – искомое количество точек.

Входные данные
В первой строке вводится одно число N (3≤N≤100000). Далее в N строках задается по паре чисел – координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.

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

Выходные данные
Выведите одно число – величину площади приведённого многоугольника.

Входные данные
Семь чисел – координаты двух точек вне прямой и коэффициенты A, B и C её нормального уравнения.

Выходные данные
Одна строка “YES”, если точки лежат по одну сторону прямой, и “NO” в противном случае.

Входные данные
Шесть чисел – координаты точки и координаты концов отрезка.

Выходные данные
Одна строка “YES”, если точка принадлежит отрезку, и “NO” в противном случае.

Входные данные
Четыре числа – коэффициенты A, B и C уравнения прямой и величина R.

Выходные данные
Три числа – коэффициенты A, B и C уравнения любой из прямых, параллельных заданной и лежащих от неё на расстоянии R.

Входные данные
Четыре числа – координаты двух невырожденных (т.е. ненулевых) векторов.

Выходные данные
Одно число – величина угла α
между векторами (0≤α≤π) с точностью до пятого знака после запятой.

Король Полигонии Трианг IV помешан на реформах. Чтобы войти в мировую историю, он решил провести территориальную реформу в своей стране. Страна Полигония имеет форму простого многоугольника, то есть ее граница не имеет самопересечений и самокасаний. В Полигонии большую роль играют внутренние диагонали — отрезки, соединяющие вершины государственной границы и полностью проходящие по территории страны, не касаясь границы. При этом форма Полигонии такова, что никакие две внутренние диагонали не лежат на одной прямой.

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

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

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

В первой строке входных данных задается число N (3 ≤ N ≤ 20) — количество вершин многоугольника, образующего границу Полигонии. В следующих N строках находятся по 2 целых числа, по абсолютной величине не превосходящих 10 000 — координаты вершин в порядке обхода многоугольника против часовой стрелки. Гарантируется, что никакие три последовательные вершины многоугольника не лежат на одной прямой, и он не имеет самопересечений и самокасаний. Также гарантируется, что никакие две диагонали, содержащиеся внутри многоугольника, не лежат на одной прямой.

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

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

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

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

Если искомых разбиений несколько, выведите любое из них.

 

Примеры

№	Входные данные	Выходные данные	Рисунок к тесту
1	4 0 0 1 0 1 1 0 1	2 1 1 1 0 0
2	10 -6 0 0 2 6 0 3 3 6 4 2 4 0 6 -2 4 -6 4 -3 3	4 3 2 4 -2 4 0 2 3 3 -3 3 0 2

Прямоугольник ABCD задан координатами своих вершин. На противоположных сторонах AB и CD заданы последовательности R1 и R2 из N точек разбиения, а на сторонах BC и AD - R3 и R4 из M точек разбиения. Нумерация элементов последовательностей R1 и R2 начинается соответственно от точек A и D, а R3 и R4 - от точек B и A. Соединив отрезками точки с одинаковыми номерами в разбиениях R1 и R2, а затем в разбиениях R3 и R4, получим разбиение Q прямоугольника ABCD на множество четырехугольников.
Построить алгоритм, определяющий четырехугольник разбиения Q с наибольшей площадью, при условии, что отрезки, соединяющие точки разбиений R1 и R2 параллельны стороне AD.
Последовательности R1, R2, R3 и R4 задаются как массивы из длин отрезков разбиения соответствующих сторон прямоугольника.
 

Маша и Петя решили выяснить, чья комната больше. Машина и Петина комнаты имеют форму прямоугольников, причем Машина комната имеет размеры \(a\) на \(b\) метров, а Петина — \(c\) на \(d\) метров.

Напишите программу, которая определит, чья комната больше: Машина или Петина.

Формат входных данных
На ввод подается четыре натуральных числа, разделенных пробелами: \(a\), \(b\), \(c\) и \(d\) (\(1 \le a, b, c, d \le 1000\)).

Формат выходных данных
Если Машина комната больше, выведите латинскую букву <<M>>. Если Петина комната больше, выведите латинскую букву <<P>>. Если комнаты ребят имеют одинаковую площадь, выведите латинскую букву <<E>>.

Даны два целых положительны числа \(a\) и \(b\).

Найдите количество различных целых положительных чисел \(c\), таких, что существует невырожденный треугольник с длинами сторон \(a\), \(b\) и \(c\).

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

Формат входных данных
На первой строке ввода находится целое число \(a\), на второй строке ввода находится целое число \(b\) (\(1 \le a, b \le 10^9\)).

Формат выходных данных
Выведите одно целое число \(k\) — количество различных целых положительных чисел \(c\), таких, что существует невырожденный треугольник с длинами сторон \(a\), \(b\) и \(c\).

Дед Мороз за ночь должен посетить N городов. У него есть двумерный план расположения всех городов. План нарисован в декартовой системе координат, в которой точкой (0, 0) обозначено место старта Деда Мороза. Каждый город на плане отмечен точкой с координатой (Xi, Yi). Также на карте обозначены M точек с координатами (Pi, Qi), в которых расположены ускорители. Чтобы успеть разнести все подарки, Дед Мороз может воспользоваться ускорителем, который увеличивает его скорость в два раза (а может им и не пользоваться).

Дед Мороз в Новогоднюю ночь начинает с места старта, посещает все N городов и возвращается обратно.

Начальная скорость Деда Мороза равна 1. Найдите наименьшее время, необходимое Деду Морозу, чтобы посетить все города и вернуться обратно. Временем, при котором он раскладывает все подарки будем пренебрегать!

Входные данные
Первая строка входных данных содержит два целых числа N и M (1 <= N <= 12, 0 <= M <=5). Следующие N строк содержат координаты городов (Xi, Yi). Далее идут M строк с координатами ускорителей (Pi, Qi). Все координаты различны и среди них нет координаты (0, 0).

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

Примеры

№	Входные данные	Выходные данные	Примечание
1	2 1 1 1 0 1 1 0	2 1 1 1 0 1 1 0	Вот один из оптимальных способов разнести все подарки Пройти расстояние 1 от начала координат до ускорителя 1 со скоростью 1, затратив время 1. Пройти расстояние 1 от ускорителя 1 до города 1 со скоростью 2, затратив время 0,5. Пройти расстояние 1 от города 1 до города 2 со скоростью 2, затратив время 0,5. Пройти расстояние 1 от города 2 до начала координат со скоростью 2, затратив время 0,5.
2	2 1 1 1 0 1 100 0	3.4142135624	Вот один из оптимальных способов разнести все подарки Пройти расстояние 1.41... от начала координат до города 1 со скоростью 1, затратив время 1.41.... Пройти расстояние 1 от города 1 до города 2 со скоростью 1, затратив время 1. Пройти расстояние 1 от города 2 до начала координат со скоростью 1, затратив время 1.
3	1 2 4 4 1 0 0 1	4.3713203436	Вот один из оптимальных способов разнести все подарки Пройти расстояние 1 от начала координат до ускорителя 1 со скоростью 1, затратив время 1. Пройти расстояние 1,41... от ускорителя 1 до ускорителя 2 со скоростью 2, затратив время 0,707.... Пройти расстояние 5 от ускорителя 2 до города 1 со скоростью 4, затратив время 1,25. Пройти расстояние 5,65... от города 1 до начала координат со скоростью 4, затратив время 1,41....

У игрока в космической стрелялке есть очень мощная лазерная пушка. Но она неподвижна и может стрелять только в одном направлении. Игрок может расставить на игровом поле двусторонние зеркала, меняющие ход луча, чтобы поражать врагов. Введём декартову систему координат с центром, где расположена пушка, то есть пушка имеет координаты (0; 0). Пушка стреляет в направлении точки (1; 1). Игрок может поставить зеркала в точках с целочисленными координатами. Зеркала могут быть горизонтальными или вертикальными, попадание луча в зеркало меняет траекторию луча по законам отражения света. Некоторые возможные варианты отражения луча от зеркала изображены на рисунке.

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

Входные данные
Программа получает на вход два целых числа X и Y , не превосходящих по модулю 10000, записанные в разных строках — координаты цели. Точка (X; Y) не совпадает с началом координат.

Выходные данные
Программа должна вывести в первой строке число N — необходимое количество зеркал. Следующие N строк должны содержать информацию о каждом зеркале. В i-й строке должны быть записаны через пробелы два целых числа xi и yi и один символ ti , обозначающие координаты (xi ; yi) точки, в которых установлено i-е зеркало, и тип этого зеркала ti . Если ti является символом «V», то i-е зеркало размещено вертикально, если же ti является символом «H», то зеркало размещено горизонтально. Например, строка «-2 5 H» обозначает горизонтальное зеркало в точке (−2; 5). Зеркала можно выводить в любом порядке. Зеркало нельзя размещать в точке (0; 0), также нельзя размещать два зеркала в одной точке. Значения xi и yi не должны по модулю превосходить 100 000. Также, разумеется, нельзя допустить, чтобы отражённый луч попал в пушку. Если вариантов ответа несколько, выведите любой из них. Если поразить цель в соответствии с условиями задачи невозможно, программа должна вывести одно число «-1». Если для поражения цели зеркала не нужны, программа должна вывести одно число «0»
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 1	1 3 3 H

Выведите все исходные точки в порядке возрастания их расстояний от начала координат.

Создайте структуру Point и сохраните исходные данные в массиве структур Point.

Входные данные
Программа получает на вход набор точек на плоскости. Сначала задано количество точек n, затем идет последовательность из n строк, каждая из которых содержит два числа: координаты точки. Величина n не превосходит 100, все исходные координаты – целые числа, не превосходящие 10³.

Выходные данные
Необходимо вывести  все исходные точки в порядке возрастания их расстояний от начала координат. Программа выводит только координаты точек, их количество выводить не надо.

 Примеры

№	Входные данные	Выходные данные
1	2 1 2 2 3	1 2 2 3

На плоскости даны N точек. Вам требуется построить выпуклую оболочку данного множества точек. Выведите два числа: периметр и площадь.

Входные данные
Первая строка содержит количество точек N, 1≤N≤10000. Каждая из последующих N строк содержит два целых числа – координаты x_i и y_i. Все числа по модулю не превосходят 10⁴.

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

Примеры

№	Входные данные	Выходные данные
1	4 0 0 3 4 3 1 6 0	16.0000000000 12.0000000000

Входные данные
В первой строке вводятся три целых числа – N (3≤N≤100000) и координаты точки. Далее в N строках задается по паре целых чисел – координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.

Выходные данные
Выведите  одну строку: “YES”, если заданная точка содержится в приведённом многоугольнике или на его границе, и “NO” в противном случае.
 

Примеры

№	Входные данные	Выходные данные
1	3 2 3 1 1  10 2 2 8	YES