Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

Перевод часов

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

В плоской стране наступила очередная зима, и нужно срочно переводиться на зимнее время! Проблема в том, что стрелка городских часов (единственная, кстати), находящихся в начале координат, очень-очень тяжёлая, и поэтому рабочие хотят узнать, в какую сторону крутить стрелку будет быстрее. Чтобы упростить вам задачу, они уже посчитали, куда указывает стрелка и куда она должна указывать. Помогите им!
 
Входные данные
В первой строке задаётся точка, куда указывает стрелка. Она задаётся координатами X1 и Y1 (\(-10 <= X_1, Y_1 <= 10\)).
Во второй строке задаётся точка, куда должна указывать стрелка. Она задаётся координатами X2 и Y2 (\(-10 <= X2, Y2 <= 10\)).
Координаты задаются вещественным типом.
 
Выходные данные
В единственной строке выведите "Clockwise", если стрелку нужно крутить по часовой стрелке, "Counter-clockwise", если её нужно крутить против часовой стрелки, и "Doesn't matter", если это займёт одинаковое время, в какую сторону её бы не крутили. Выводить фразы следует без кавычек.

 

Примеры
№ Входные данные Выходные данные
1
1 0
-1 1
 Counter-clockwise

Ленивый Вася и релиз Half-Life 3

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

Свершилось чудо! Наконец-то вышел долгожданный Half-Life 3, о котором мечтали миллионы людей по всему миру! Вася тоже с нетерпением ждал продолжения легендарной серии, и даже не ел в школьной столовой целый месяц, чтобы ему хватило на покупку этого шедевра! Единственная проблема, которая стоит у него на пути - огромное домашнее задание по алгебре. В классе он прошёл новую тему - прямые, и теперь ему нужно сделать аж N задач на построение прямой через 2 точки. Но ведь так хочется поиграть, а на следующий день рассказывать друзьям, какой же там классный графон... Поэтому он попросил Вас, своего друга, помочь ему.
 
Входные данные
В первой строке вводятся координаты первой точки (X1, Y1), (\(-50 <= X_1, Y_1 <= 50\)).
Во второй строке вводятся координаты второй точки (X2, Y2), (\(-50 <= X_2, Y_2 <= 50\)).
 
Выходные данные
В единственной строке выведите подряд 3 целых числа: коэффициенты a, b, c уравнения прямой.
 
Примечание: если у вас не заходит задача, но вы уверены, что всё правильно - попробуйте умножить все коэффициенты на -1. Задача предполагает, что вы использовали формулы, взятые с лекции/теории.

 

Примеры
№ Входные данные Выходные данные
1
-1 -1
1 1
 -2 2 0

Пикап-мастер

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

Недавно Венцеслав прочитал новую книгу по пикапу, и теперь он хочет опробовать свои знания в парке. Для простоты представим парк в виде набора тропинок, которые являются отрезками на плоскости. Венцеслав уже гулял в этом парке, и знает, какая девушка по какой тропинке гуляет. Проблема в том, что Венцеслав очень ленивый, и гуляет только по одной тропинке. А ещё ему лень узнать, каких девушек он может встретить по пути, и поэтому он попросил Вас, своего лучшего друга, помочь ему в этом непростом деле.
 
Входные данные
В первой строке вводятся координаты концов тропинки (X1, Y1) и (X2, Y2), по которой гуляет Венцеслав (\(-20 <= X1, Y1, X2, Y2 <= 20\)).
Во второй строке вводится целое число N - количество тропинок, по которым гуляют девушки (\(0  <= N <= 5\)).
В последующих N строках вводятся координаты концов тропинок, по которым гуляют девушки (Xi1, Yi1) и (Xi2, Yi2), по i-ой тропинке гуляет i-ая девушка (\(-20 <= X_{i1}, Y_{i1}, X_{i2}, Y_{i2}  <= 20\))
Координаты концов тропинок - вещественные числа.
 
Выходные данные
В первой строке выведите число M - количество девушек, пути которых пересекутся с путём Венцеслава (касание путей считается пересечением).
Во второй строке выведите M чисел - номера девушек, с которыми встретится наш герой. Девушки нумеруются с единицы!
 
Примеры
№ Входные данные Выходные данные
1
0 0 2 2
1
0 2 2 0
 1
1

 

Площадь треугольника

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

Входные данные
Шесть чисел – координаты трёх вершин треугольника.
 
Выходные данные
Одно число – величина площади треугольника.
 
Примеры
№ Входные данные Выходные данные
1 1 1 2 4 3 2 2.50000

Принадлежность точки лучу

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

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

 

Примеры
№ Входные данные Выходные данные
1 4 0 4 2 4 5 NO

Сумма штрафа

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

Новый градоначальник города Глупова решил с целью пополнения бюджета и экономии горючего провести кампанию борьбы с левым уклоном и левыми рейсами. Для этого он запретил водителям выполнять левые повороты, установив штраф за каждый поворот налево в размере одного миллиона (разворот поворотом налево не считается).
 
От тяжелого прошлого Глупову достались улицы, которые могут пересекаться под любыми углами. Градоначальник приказал установить компьютерную систему тотальной слежки, которая следит за каждым автомобилем, записывая его координаты каждый раз, когда тот меняет направление движения (включая начальную и конечную точки пути).
 
Требуется написать программу, вычисляющую по записанной последовательности координат автомобиля штраф, который должен быть взыскан с водителя.
 
Входные данные
В первой строке вводится целое число N - количество записанных пар координат (\(1 <= N <= 1000\)). В каждой из следующих N строк записана очередная из этих пар (вещественные числа).
 
Выходные данные
Выведите суммарный штраф водителя в миллионах.

 

Примеры
№ Входные данные Выходные данные
1
4
0 0
1 0
1 1
2 1
 1

В каком ухе жужжит?

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

Фрекен Бок находится в точке \(A(x_a, y_a)\) и, глядя прямо на Малыша, стоящего в точке \(B(x_b, y_b)\) задает вопрос: «В каком ухе у меня жужжит?». Естественно, у грозной домоправительницы жужжит в ухе, потому что в точке \(C(x_c, y_c)\) завис Карлсон со включенным мотором. Определите, какой ответ Малыша будет правильным.
 
Входные данные
С клавиатуры вводятся координаты точек A, B и С. Исходные данные являются целыми числами, по модулю не превышающими 1000.
 
Выходные данные
Выведите слово LEFT (заглавными буквами), если у домоправительницы жужжит в левом ухе, RIGHT – если в правом, BOTH – если  жужжание и в левом и в правом одинаково.

 

Примеры
№ Входные данные Выходные данные
1 0 0 1 0 0 1 LEFT

Полярный угол точки

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

Даны два числа - координаты точки, не совпадающей с началом координат. Найти полярные координаты точки, не совпадающей с началом координат.

Входные данные
Во входной строке содержится два целых числа - координаты точки. Числа целые, по модулю не превышающее 1000.

Выходные данные
Одно число - величина ее полярного угла (в радианах). Значение полярного угла должно принадлежать интервалу [0; 2*π).

 

Примеры
№ Входные данные Выходные данные
1 2 3 0.98279

Зеркала

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

Однажды злой волшебник Сарумян поглядел в видеочат и узрел там систему из N зеркал. Долго думал он, прежде чем внутренний голос подсказал ему, что система не простая. Он понял, что если посмотреть на эту систему под некоторым углом, и увидеть заданную точку А через все N зеркал (то есть так, чтобы его взгляд отразился через каждое из них ровно по одному разу, а потом попал в точку A), то откроются ему все тайны интернета. 
Однако светлые силы не дремали и через агентурную сеть выяснили все про этот видеочат. 
Требуется написать программу, которая подсказала бы светлым силам, под каким углом нужно посмотреть на систему зеркал, чтобы узнать все тайны интернета.

Входные данные:
В первой строке входного файла записано одно число – количество зеркал (0<N≤10). В следующей строке записаны координаты (x и y, где ось x направлена вправо, ось y – вверх) исходной точки (откуда надо смотреть на зеркала) и точки A. Далее в N строках записана информация о зеркалах – по четыре числа, обозначающие координаты начала и конца зеркала. Отражающая поверхность расположена на левой стороне зеркала (если смотреть от первой точки в направлении второй). С обратной стороны зеркала прозрачны.
Причем выполняются следующие ограничения:
•    Все координаты вещественны и по модулю не превосходят 10000
•    Никакие зеркала не пересекаются 
•    Конечная и начальная точки не лежат ни на одном из зеркал

Выходные данные:
В первую строку выходного файла необходимо записать YES, если решение существует, и NO, если нет. Если решение есть, то во вторую строку надо записать угол в градусах (с точностью до шести знаков после запятой), под которым нужно смотреть на зеркала. Угол отсчитывается против часовой стрелки от оси Ox и лежит в пределах от 0 до 360 градусов.

Примеры
№ Входные данные Выходные данные
1 2 
0 0
0 5
1 0 1 2
-1 4 –1 2		 YES
51.340192

Треугольник. Поиск вершины по положению центроида

Бинарный поиск Элементарная геометрия Вычислительная геометрия

Точка G – центр пересечения медиан треугольника (центроид) АВС.
Найдите абсциссу вершины C (координату x), если известно:
- координаты точек A и B;
- координата точки D, лежащей на прямой ВС;
- точка G лежит на прямой ED (координаты точки E известны);
- для координат выполняются условия: Ax<Cx<Bx;
Входные данные: в 1-й строке вводятся значения Ax, Ay, Bx, By Dx,Dy, Ex, Ey – координаты точек A, B, D, E
Все значения целые числа в интервале [-1000;1000].
Выходные данные: ответ на задание с точностью не менее 10-5.
Пример:

Входные данные Выходные данные
2 2 7 1 6 3 3 4 3.6
0 0 5 1 3 4 0 0 1.0

Поиск вершины по ортоцентру (H)

Бинарный поиск Элементарная геометрия Вычислительная геометрия

Точка H – центр пересечения высот треугольника (ортоцентр) АВС.
Найдите абсциссу вершины C (координату x), если известно:
- координаты точек A и B;
- координата точки D, лежащей на прямой ВС;
- точка H лежит на прямой ED (координаты точки E известны);
- для координат выполняются условия: Ax<Cx<Bx;
Входные данные: в 1-й строке вводятся значения Ax, Ay, Bx, By Dx,Dy, Ex, Ey – координаты точек A, B, D, E
Все значения целые числа в интервале [-1000;1000].
Выходные данные: ответ на задание с точностью не менее 10-5.
Пример:

Входные данные Выходные данные
1 1 6 3 9 1 1 5 2.454545
1 2 5 1 6 -1 1 5 3.196078

Поиск вершины по центру описанной окружности (O)

Бинарный поиск Элементарная геометрия Вычислительная геометрия

Точка O – центр описанной окружности треугольника АВС.
Найдите абсциссу вершины C (координату x), если известно:
- координаты точек A и B;
- координата точки D, лежащей на прямой ВС;
- точка O лежит на прямой ED (координаты точки E известны);
- для координат выполняются условия: Ax<Cx<Bx;
Входные данные: в 1-й строке вводятся значения Ax, Ay, Bx, By Dx,Dy, Ex, Ey – координаты точек A, B, D, E
Все значения целые числа в интервале [-1000;1000].
Выходные данные: ответ на задание с точностью не менее 10-5.
Пример:

Входные данные Выходные данные
1 1 6 3 7 1 0 6  3.784
1 2 5 1 6 -1 1 5 3.207692

Поиск вершины по центру вписанной окружности (I, инцентр)

Бинарный поиск Элементарная геометрия Вычислительная геометрия

Точка I – центр вписанной окружности треугольника АВС (инцентр).
Найдите абсциссу вершины C (координату x), если известно:
- координаты точек A и B;
- координата точки D, лежащей на прямой ВС;
- точка I лежит на прямой ED (координаты точки E известны);
- для координат выполняются условия: Ax<Cx<Bx;
Входные данные: в 1-й строке вводятся значения Ax, Ay, Bx, By Dx,Dy, Ex, Ey – координаты точек A, B, D, E
Все значения целые числа в интервале [-1000;1000].
Выходные данные: ответ на задание с точностью не менее 10-5.
Пример:

Входные данные Выходные данные
1 1 7 3 8 1 1 7 4.348182
-1 3 9 1 8 -1 -1 1  6.500895

Кардиоида

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

Кардиоида-- плоская алгебраическая кривая 4-го порядка, которая описывается фиксированной точкой окружности радиуса , катящейся по неподвижной окружности с таким же радиусом

В прямоугольной декартовой системе координат уравнение кривой имеет вид:

Найдите координаты точки пересечения кардиоиды и отрезка EF, если известно:
- коэффициент кардиоиды a;
- координаты вершин отрезка EF;
гарантируеся, что одна из вершин отрезка лежит внутри кардиоиды, а другая снаружи.
Рассмотрим функцию F(x,y,a)= (x2+y2+2ax)2-4a2(x2+y2). Если для точки M с координатами (x,y) F(x,y,a)<0, то точка M лежит внутри кардиоды с параметром a. Если значение функции будет положительным, то точка M лежит снаружи.

Входные данные:
-в 1-й строке вводится вещественное число - значениe коэффициента кардиоды a (по модулю не более 10)
-в 2-й строке вводятся целые значения Ex, Ey, Fx, Fy – координаты вершин отрезка  EF (числа в интервале [-1000;1000]).
Выходные данные:
1 строка  - абцисса точки пересечения (координата x), с точностью не менее 10-5 
2 строка  - ордината точки пересечения (координата y), с точностью не менее 10-5 

Пример:
Входные данные Выходные данные
1.0
-1 1 1 3		 0
2
-2.5
10 4 1 1		 8.91545419
3.63848473

Сфера и отрезок

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

Найдите точку пересечения отрезка AB и сферы радиуса R, с центром в точке O . Все точки заданы декартовыми координатами в пространстве. Гарантируеся, что только одна из вершин отрезка расположена внутри сферы.
Входные данные
В 1-й строке вводятся числа чисел, разделённых пробелами. Вначале вводится радиус сферы R, затем  координаты центра сферы
 O (Ox,Oy,Oz).
В 2-й строке вводятся шесть чисел, разделённых пробелами. Вначале вводятся координаты точки A (Ax,Ay,Az),  затем координаты точки
B (Bx,By,Bz).
Выходные данные
Выводится три числа - координаты точки пересечения. Каждая координата в отдельной строке и с точностью не менее 10-6.
Пример 1:

Входные данные Выходные данные
10 0 0 0
7 6 5 2 4 6		 6.37704215657
5.75081686263
5.12459156869
Пример 2:
Входные данные Выходные данные
8 1 -1 2
5 6 -5 2 -4 6		 4.45729353069
4.19097843564
-3.0100762792

Эллипс и отрезок

Информатика Бинарный поиск Вычислительная геометрия

Найдите координаты точки пересечения эллипса и отрезка, если известно:
- координаты точек фокусов эллипса A, B;
- R - сумма расстояний от точки эллипса до фокусов;
- координаты вершин отрезка EF;
гарантируеся, что одна из вершин отрезка лежит внутри эллипса, а другая снаружи
Входные данные:
-в 1-й строке вводятся значения Ax, Ay, Bx, By, R – координаты точек A, B и сумма расстояний R
-в 2-й строке вводятся значения Ex, Ey, Fx, Fy – координаты вершин отрезка  EF
Все значения целые числа в интервале [-1000;1000].
Выходные данные:
1 строка  - абцисса точки пересечения (координата x), с точностью не менее 10-5 
2 строка  - ордината точки пересечения (координата y), с точностью не менее 10-5 

Пример:

Входные данные Выходные данные
-10 3 -2 7 12
-14 -9 -8 6		 -10
1
3 3 6 7 7
3 4 -1 7		 1.7670862633
4.9246853025

Описанный четырехугольник

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

Известно, что вокруг выпуклого четырехугольника ABCD можно описать окружность.
Найдите площадь четырехугольника ABCD, если известно:
- координаты точек A, B, C;
- точка D принадлежит отрезку EF
Входные данные:
-в 1-й строке вводятся значения Ax, Ay, Bx, By Cx,Cy – координаты точек A, B, C
-в 2-й строке вводятся значения Ex, Ey, Fx, Fy – координаты вершин отрезка  EF
Все значения целые числа в интервале [-1000;1000].
Выходные данные: ответ на задание с точностью не менее 10-5.
Пример:

Входные данные Выходные данные
1 2 8 1 10 5
5 8  14 11		 36.0
3 2 4 6 9 1
5 1 0 0		 15.797687719

Расстояние между отрезками - 3

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

Найдите расстояние между отрезками AB и CD. Отрезки заданы декартовыми координатами границ в пространстве.
Расстояние между отрезками - минимальное расстояние между точками X,Y, где \(X \in [A,B], \ Y\in[C,D]\).
Входные данные
В 1-й строке вводятся шесть чисел, разделённых пробелами. Вначале вводятся координаты точки A (Ax,Ay,Az),  затем координаты точки B (Bx,By,Bz).
В 2-й строке вводятся шесть чисел, разделённых пробелами. Вначале вводятся координаты точки C (Cx,Cy,Cz),  затем координаты точки D (Dx,Dy,Dz).
Выходные данные
Выводится одно число - расстояние между отрезками AB, CD.
Расстояние необходимо найти с точностью не менее 10-6.
Пример 1:

Входные данные Выходные данные
-7 8 6 -6 -5 8
-7 8 6 0 -8 9		 0.0
Отрезки имеют общую точку, поэтому расстояние равно 0.0
Пример 2:
Входные данные Выходные данные
-10 -10 -8 10 7 9
-7 4 0 2 -8 -2		 0.14477985167371404

Дом у дороги

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

Министерство дорожного транспорта решило построить себе новый офис. Поскольку министр регулярно выезжает с инспекцией наиболее важных трасс, было решено, что офис министерства не должен располагаться слишком далеко от них.
 
Наиболее важные трассы представляют собой прямые на плоскости. Министерство хочет выбрать такое расположение для своего офиса, чтобы максимум из расстояний от офиса до трасс был как можно меньше.
 
Требуется написать программу, которая по заданному расположению наиболее важных трасс определяет оптимальное расположение дома для офиса министерства дорожного транспорта.
 
Входные данные
Первая строка входного файла содержит одно целое число n — количество наиболее важных трасс (1  ≤ n ≤ 104 ).
 
Последующие n строк описывают трассы. Каждая трасса описывается четырьмя целыми числами x1, y1, x2 и y2 и представляет собой прямую, проходящую через точки (x1, y1)  и (x2, y2) . Координаты заданных точек не превышают по модулю 104. Точки (x1 , y1)  и (x2 , y2)  ни для какой прямой не совпадают.
 
Выходные данные
Выходной файл должен содержать два разделенных пробелом вещественных числа: координаты точки, в которой следует построить офис министерства дорожного транспорта. Координаты по модулю не должны превышать 109, гарантируется, что хотя бы один такой ответ существует. Если оптимальных ответов несколько, необходимо выведите любой из них.
 
Ответ должен иметь абсолютную или относительную погрешность не более 10−6, что означает следующее. Пусть максимальное расстояние от выведенной точки до некоторой трассы равно x, а в правильном ответе оно равно y. Ответ будет засчитан, если значение выражения | x − y | /  max(1, |y| )  не превышает 10−6.
 
 
Ввод Вывод
4
0 0 0 1
0 0 1 0
1 1 2 1
1 1 1 2
 0.5000000004656613 0.4999999995343387
7
376 -9811 376 -4207
6930 -3493 6930 -8337
1963 -251 1963 -5008
-1055 9990 -684 9990
3775 -348 3775 1336
7706 -2550 7706 -8412
-9589 8339 -4875 8339
 4040.9996151750674 12003.999615175067

 Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2011, 2 день, Задача D 

Точка пересечения медиан

Вычислительная геометрия Элементарная геометрия Многоугольники. Выпуклые оболочки

Точка пересечения медиан

Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3.
Все числа целые, по модулю не превосходят 1000.

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

Примеры:
Входные данные Выходные данные 
1 1 2 4 3 2
 
2.00000 2.33333
 
2 4 3 2 1 1 
2.00000 2.33333

 

Точка пересечения высот

Вычислительная геометрия Элементарная геометрия Многоугольники. Выпуклые оболочки

Точка пересечения высот

Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3.
Все числа целые, по модулю не превосходят 1000.

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

Примеры:
Входные данные Выходные данные 
1 1 2 4 3 2
 
3.0 2.0
 
10 0 12 2 14 5
 
 37.0 -18.0

 

Вписанная окружность

Вычислительная геометрия Элементарная геометрия Многоугольники. Выпуклые оболочки

Вписанная окружность

Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3.
Все числа целые, по модулю не превосходят 1000.

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

Примеры:
Входные данные Выходные данные
1 1 2 4 3 2 
2.12132 2.292893 0.65493
 
10 0 12 2 14 5
 
 11.878925  2.099258  0.1557984


 
 

Описанная окружность

Вычислительная геометрия Элементарная геометрия Многоугольники. Выпуклые оболочки

Описанная окружность

Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3.
Все числа целые, по модулю не превосходят 1000.

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

Примеры:
Входные данные Выходные данные
1 1 2 4 3 2 
1.50000 2.50000 1.58114
 
10 0 12 2 14 5
 
-0.50000 12.50000 16.32483


 

 
 

Точка пересечения двух прямых

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

Точка пересечения прямых

На плоскости даны две прямые. Каждая прямая задается парой точек, через которые она проходит.
Требуется установить, пересекаются ли эти прямые, и найти координаты точки пересечения.
Входные данные
Вводятся сначала координаты двух различных точек, через которые проходит первая прямая,
а затем - координаты еще двух различных (но, быть может, совпадающих с первыми двумя) точек,
через которые проходит вторая прямая. Координаты каждой точки - целые числа, по модулю не превышающие 1000.
Выходные данные
Если прямые не пересекаются, выведите одно число 0. Если прямые совпадают, выведите 2.
Если прямые пересекаются ровно в одной точке, то выведите сначала число 1,
а затем два вещественных числа - координаты точки пересечения.
Координаты точки пересечения необходимо определить с точностью не менее 5 знаков.

Примеры

входные данные выходные данные 
0 0 1 1
1 0 -1 2
 
1  0.50  0.50
 
1 2 3 4
0 3 4 7
 
0
 
1 2 3 4
3 4 1 2
 2

Расстояние от точки до прямой

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

Расстояние от точки до прямой

Определите расстояние от точки до прямой.
Входные данные
Пять чисел – координаты точки и коэффициенты A, B и C уравнения прямой.
Все числа целые и по модулю не превосходят 10000.
Выходные данные
Одно число – расстояние от точки до прямой. Точность вычисления не менее 5 знаков.

Примеры

входные данные выходные данные 
1 5 0 -4 8
 3.0 
1 5 -4 0 8 
 
1.0

Описанная окружность

Вычислительная геометрия Элементарная геометрия Многоугольники. Выпуклые оболочки

Описанная окружность

Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3.
Все числа целые, по модулю не превосходят 1000.

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

Примеры:
Входные данные Выходные данные
1 1 2 4 3 2 
1.50000 2.50000 1.58114
 
10 0 12 2 14 5
 
-0.50000 12.50000 16.32483


 

 
 

Вписанная окружность

Вычислительная геометрия Элементарная геометрия Многоугольники. Выпуклые оболочки

Вписанная окружность

Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3.
Все числа целые, по модулю не превосходят 1000.

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

Примеры:
Входные данные Выходные данные
1 1 2 4 3 2 
2.12132 2.292893 0.65493
 
10 0 12 2 14 5
 
 11.8789  2.099258  0.1557984


 
 

Приданое для Василисы

Вычислительная геометрия Элементарная геометрия Многоугольники. Выпуклые оболочки

Приданое для Василисы

Тридевятое царство царя Василия имеет треугольную форму. Он решил выдать замуж свою любимую дочь Василису и отдать ей в приданое часть своего царства. Царь Василий очень любит геометрию, поэтому вначале выполнил на карте царства следующие действия:
- из самого большого угла царь провел высоту к противоположной стороне;
- в самом маленьком угле царь провел биссектрису;
- из среднего угла царь провел медиану;
Образовавшийся треугольник царь решил отдать в приданое.
Зная координаты вершин царства, определите отношение площади предпологаемого приданого к площади всего царства.
Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3.
Это координаты "вершин" царства. Все числа целые, по модулю не превосходят 1000.

Выходные данные
Выведите одно число - отношение площадей приданого и царства. 
Ответе должен быть выдан с точностью не менее 5 знаков.

Примеры:
Входные данные Выходные данные 
0 1 -2 3 8 3
 0.07324155 
-1 2 10 11 0 1

  0.1600294

Приданое для Елены

Вычислительная геометрия Элементарная геометрия Многоугольники. Выпуклые оболочки

Приданое для Елены

Тридевятое царство царя Егора имеет треугольную форму. Он решил выдать замуж свою любимую дочь Елену и отдать ей в приданое часть своего царства. Царь Егор очень любит геометрию, поэтому вначале выполнил на карте царства следующие действия:
- из самого большого угла царь провел высоту к противоположной стороне;
- в среднем угле царь провел биссектрису;
- из самого маленького угла царь провел медиану;
Образовавшийся треугольник царь решил отдать в приданое.
Зная координаты вершин царства, определите отношение площади предпологаемого приданого к площади всего царства.
Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3.
Это координаты "вершин" царства. Все числа целые, по модулю не превосходят 1000.

Выходные данные
Выведите одно число - отношение площадей приданого и царства. 
Ответе должен быть выдан с точностью не менее 5 знаков.

Примеры:
Входные данные Выходные данные 
0 1 -2 3 8 3
 0.0003479 
-1 2 10 11 0 1

  0.01717956

Приданое для Ирины

Вычислительная геометрия Элементарная геометрия Многоугольники. Выпуклые оболочки

Приданое для Ирины

Тридевятое царство царя Игоря имеет треугольную форму. Он решил выдать замуж свою любимую дочь Елену и отдать ей в приданое часть своего царства. Царь Игорь очень любит геометрию, поэтому вначале выполнил на карте царства следующие действия:
- из самого большого угла царь провел высоту к противоположной стороне;
- в среднем угле царь провел биссектрису;
- из самого большого угла царь провел медиану;
Образовавшийся треугольник царь решил отдать в приданое.
Зная координаты вершин царства, определите отношение площади предпологаемого приданого к площади всего царства.
Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3.
Это координаты "вершин" царства. Все числа целые, по модулю не превосходят 1000.

Выходные данные
Выведите одно число - отношение площадей приданого и царства. 
Ответе должен быть выдан с точностью не менее 5 знаков.

Примеры:
Входные данные Выходные данные 
0 1 -2 3 8 3
0.06349376 
-1 2 10 11 0 1

 0.0739834

Столица царя Иосифа

Вычислительная геометрия Элементарная геометрия Многоугольники. Выпуклые оболочки

Столица царя Иосифа

Тридевятое царство царя Иосифа имеет треугольную форму. Столица царства расположена в центроиде треугольника (точка О). Царь Иосиф решил построить новую столицу.  Царь очень любит геометрию, поэтому вначале выполнил на карте царства следующие действия:
- из самого большого угла царь провел высоту и определил её основание (точку D);
- в среднем угле царь провел биссектрису и определил её основание (точку E);
- из самого маленького угла царь провел медиану и определил её основание (точку F);
Новую столицу царь Иосиф решил расположить в центроиде треугольника  DEF (точка G).
Зная координаты вершин царства, определите расстояние между столицами царства (длина отрезка GO).
Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3.
Это координаты "вершин" царства. Все числа целые, по модулю не превосходят 1000.

Выходные данные
Выведите одно число - ответ на задачу. 
Ответе должен быть выдан с точностью не менее 5 знаков.

Примеры:
Входные данные Выходные данные 
0 1 -2 3 8 3
1.75530286 
-1 2 10 11 0 1

 4.24704495

Описанная окружность

Вычислительная геометрия Элементарная геометрия Многоугольники. Выпуклые оболочки

Описанная окружность

Входные данные
Даны координаты трех точек, не лежащих на одной прямой: X1, Y1, X2, Y2, X3, Y3.
Все числа целые, по модулю не превосходят 1000.

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

Примеры:
Входные данные Выходные данные
1 1 2 4 3 2 
1.50000 2.50000 1.58114
 
10 0 12 2 14 5
 
-0.50000 12.50000 16.32483


 

 
 

ЛА-0107_Расстояние от точки до прямой

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

Расстояние от точки до прямой

Определите расстояние от точки до прямой.
Входные данные
Пять чисел – координаты точки и коэффициенты A, B и C уравнения прямой.
Все числа целые и по модулю не превосходят 10000.
Выходные данные
Одно число – расстояние от точки до прямой. Точность вычисления не менее 5 знаков.

Примеры

входные данные выходные данные 
1 5 0 -4 8
 3.0 
1 5 -4 0 8 
 
1.0

ЛА-0107a_Расстояние от точки до прямой-2

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

Расстояние от точки до прямой-2

Дана линейная функция f(x,y)=ax+by+C и точка K=(x0,y0).
Известно, что f(a,b)=D, f(x0,y0)=E.
Найдите расстояние от точки K до прямой f(x,y)=0.
Входные данные
Три числа – С (свободный член уравнения прямой и значения функци (D,E). 
Все числа целые и по модулю не превосходят 109.
Выходные данные
Одно число – расстояние от точки K до прямой. Если таких значений несколько, то выведите любое.
Если задача  не имеет решения, то выведите -1. Точность вычисления не менее 10-6 знаков.

Примеры

входные данные выходные данные 
1 10 6
   2 
10 1 6 
 
 -1

Точка пересечения двух прямых

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

Точка пересечения прямых

На плоскости даны две прямые. Каждая прямая задается парой точек, через которые она проходит.
Требуется установить, пересекаются ли эти прямые, и найти координаты точки пересечения.
Входные данные
Вводятся сначала координаты двух различных точек, через которые проходит первая прямая,
а затем - координаты еще двух различных (но, быть может, совпадающих с первыми двумя) точек,
через которые проходит вторая прямая. Координаты каждой точки - целые числа, по модулю не превышающие 1000.
Выходные данные
Если прямые не пересекаются, выведите одно число 0. Если прямые совпадают, выведите 2.
Если прямые пересекаются ровно в одной точке, то выведите сначала число 1,
а затем два вещественных числа - координаты точки пересечения.
Координаты точки пересечения необходимо определить с точностью не менее 5 знаков.

Примеры

входные данные выходные данные 
0 0 1 1
1 0 -1 2
 
1  0.50  0.50
 
1 2 3 4
0 3 4 7
 
0
 
1 2 3 4
3 4 1 2
 2

Вид из окна

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

На протяжении многих лет Вася работает программистом в одной очень большой и очень из- вестной компании. Эта компания обеспечивает своих сотрудников всем необходимым для приятной и плодотворной работы: бесплатными обедами, транспортом от дома до места работы и многим, многим другим. И вот в один прекрасный солнечный день Вася понял, что ему очень наскучил вид из окна его офиса, и ему нужно, чтобы за окном было что-то новое и прекрасное. А что может быть лучше чудесного горного пейзажа? Придя к этой мысли, Вася попросил своего менеджера подобрать себе новый офис с красивым видом на горы.

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

Более формально, вид из окна офиса представляет собой набор горных цепей, пронумерованных от 1 до N, где горная цепь с номером i представляет собой ломаную на плоскости из li звеньев с вершинами в точках (xi,j , yi,j ), причем для любых i, j выполнено xi,j < xi,j+1.

Кроме этого, окно в офисе имеет фиксированную ширину, поэтому все горные цепи начинаются и заканчиваются на одной вертикали, то есть существуют такие числа A и B, что для любого номера i горной цепи выполнено xi,0 = A, xi,li = B.

Отметим, что из определения горной цепи следует, что для любого значения абсциссы A <= x <= B на ломаной с номером i существует единственная точка (x, yi(x)) с этим значением абсциссы, при- надлежащая этой ломаной. Будем говорить, что горная цепь i находится строго выше горной цепи j в точке x, если выполнено строгое неравенство yi(x) > yj (x).

Естественно считать, что цепь под номером i пересекается с цепью под номером j, если су- ществуют такие два значения абсциссы x1, x2, что цепь i находится строго выше цепи j в точке x1, но при этом цепь j находится строго выше цепи i в точке x2, то есть выполнены неравенства yi(x1) > yj (x1) и yj (x2) > yi(x2). Обратите внимание на поясняющие рисунки, расположенные в примечании к задаче.

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

Формат входных данных 
В первой строке входных данных через пробел идут два целых числа: A и B (−109<=A < B<=109 ).
Во второй строке входных данных находится единственное число N — количество горных цепей, видимых из окна подобранного менеджером Васи офиса (1 <= N <= 100 000).
Далее следуют описания N горных цепей. В первой строке i-го описания содержится число li => 1 — количество звеньев ломаной, из которых состоит соответствующая горная цепь. В следую- щих li + 1 строках описания содержатся два целых числа — координаты (xi,j , yi,j ) вершин ломаной (0 <= j <= li). Суммарное число звеньев всех ломаных не превосходит 200 000.
Гарантируется, что для каждой горной цепи вершины соответствующей ей ломаной идут во входных данных в порядке возрастания абсциссы, причем для любого i выполнено xi,0 = A, xi,li = B.

Формат выходных данных 
Если же офис подходит Васе, то есть никакие две горные цепи из входных данных не пересека- ются, в единственной строке выходных данных выведите слово "Yes" (без кавычек).
Иначе выведите в первой строке слово "No" (без кавычек), а на следующей строке выведите два числа — номера двух пересекающихся горных цепей. Горные цепи нумеруются согласно их появлению во входных данных, начиная с 1.

Примеры

Ввод Вывод
-3 3
2
1
-3 2
3 1
2
-3 2
0 4
3 2		 Yes
0 4
2
3
0 3
1 3
3 1
4 1
1
0 2
4 2		 No
1 2


Замечание

Напоминаем, что абсциссой точки называется её x-координата, а ординатой — её y-координата. В первом примере хотя ломаные и касаются друг друга в точке (−3, 2), но, согласно данному выше определению, они не пересекаются. Во втором примере в точке x1 = 1 одна ломаная выше другой, а в точке x2 = 3 — наоборот, то есть горные цепи пересекаются.

 

Линейная классификация

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


В машинном обучении часто возникает задача линейной классификации объектов, когда классы объектов разделяются между собой линейной поверхностью. Например, у нас есть информация о количестве дней с момента регистрации аккаунта в социальной сети и количество отправленных сообщений за последний
день, а также информация о том, является ли этот аккаунт спам-ботом. Возраст аккаунта мы можем взять за X координату точки, а количество сообщений  за Y
коордианату. Задача классификации состоит в том, чтобы провести какую-либо прямую так, чтобы объекты одного типа находились по одну сторону этой прямой, а объекты другого типа  по другую.
 
При наличии такой прямой мы сможем пронозировать тип даже незнакомого объекта по известному возрасту аккаунта и количеству отправленных сообщений в зависимости от того, с какой стороны от прямой оказался объект. Естественно, в реальных данных могут быть ошибки измерений или необычные объекты и провести такую прямую не всегда возможно, потому что, например, объект первого типа может случйно попасть в скопление объектов второго типа и отделить его прямой невозможно.
 
Вам необходимо по информации о параметрах и типе объектов определить, существует ли прямая, которая однозначно разделеят классы объектов. Прямая не должна проходить ни через один объект.
 
Формат входных данных
В этой задаче входной файл содержит несколько тестовых блоков.
В первой строке задано число T  количество тестовых блоков (1 <= T <= 100).
Каждый тестовый блок состоит из числа N  количество описанных объектов (1 <= N <= 2000).
В следующих N строках содержится описания объектов, состоящие из трех целых чисел X, Y , Type (0 <= X, Y <= 107 , 0 <= Type <= 1).

Формат выходных данных
Выведите T слов "YES" или "NO" по одному в строке для каждого из тестовых блоков. "YES" необходимо выводить если разделение на классы возможно, "NO"  если невозможно.

Система оценки
Решения, верно работающие при T <= 10, N <= 100, будут набирать не менее половины баллов.

Ввод Вывод
2
6
1 1 1
1 2 1
1 3 0
2 1 1
2 2 0
3 1 0
6
1 3 0
2 2 0
1 2 1
3 1 1
2 1 1
1 1 0		 YES
NO

Fencing the Herd

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

Фермер Джон нуждается в вашей помощи. Он решил построить изгородь в форме прямой, чтобы ограничить движение своих коров. Он рассматривает несколько вариантов размещения изгороди и с вашей помощью хочет определить наиболее подходящий. Подходящим считается вариант, когда все коровы находятся по одну сторону изгороди. Изгородь не считается подходящей, если хоть одна корова расположена на изгороди. ФД будет задавать вам вопросы про варианты изгороди, на которые вы должны отвечать YES, если изгородь подходит и NO, в противном случае.
 
Кроме того, ФД может добавить новых коров в стадо. С того момента, как корова добавлена, она должна быть по одну сторону от изгороди со всеми другими коровами.
 
Входные данные 
Первая строка ввода содержит N (1 <= N <= 100000) и Q (1 <= Q <= 100000) разделённые одним пробелом. Это, соответственно, начальное количество коров в стаде и количество запросов.
Следующие N строк описывают начальное положение стада. Каждая строка содержит два целых числа x и x (разделённые пробелом), представляющие позицию очередной коровы.
Оставшиеся Q строк содержат запросы, либо добавляющие новую корову в стадо, либо проверяющие изгородь на применимость. Строка вида 1 x y означает, что новая корова добавляется в стадо на позицию x y. Строка вида 2 A B C означает, что ФД хочет проверить изгородь, описываемую прямой Ax+By=C.
Все позиции коров уникальны (-109 <= x, x <= 109). Кроме того, -109 <= A, B <= 109 и -1018 <= C <= 1018. Никогда не будет изгороди с A = B = 0.
 
Выходные данные
Для каждой изгороди выведите YES, если она подходит и NO, в противном случае.
 
Ввод Вывод
3 4
0 0
0 1
1 0
2 2 2 3
1 1 1
2 2 2 3
2 0 1 1
YES
NO
NO
 
Прямая 2x + 2y = 3 оставляет начальные 3 коровы по одну сторону. Однако корова (1,1) на другой стороне, поэтому после её добавления такая изгородь уже не подходит. Прямая Y=1 не подходит, поскольку коровы (0,1) и (1,1) находятся на ней.
 
Предупреждение: ввод-вывод для этой задачи очень большой. В С++ можно использовать scanf или ios_base::sync_with_stdio(false). В Java надо не использовать java.util.Scanner. Не делайте flush вывода (например? используя std::endl) после каждого запроса.

Cow Curling

Вычислительная геометрия Динамическое программирование Структуры данных

В коровий кёрлинг вовлечены две команды, каждая из которых двигает N тяжёлых камней (3 <= N <= 50,000) по льду. В конце игры имеется 2N камней на льду, каждый из которых расположен в различной точке
плоскости.  
 
Подсчёт очков в коровьем кёрлинге ведётся следующим образом:
Камень считается «захваченным», если он содержится внутри треугольника, по углам которого находятся камни противника (камень, который находится на границе такого треугольника, также считается захваченным). Счёт команды есть количество камней команды противника, которые «захвачены».
 
Вычислите финальный счёт матча по коровьему кёрлингу, по заданному расположению всех камней.
 
 
INPUT FORMAT:
 
* Строка 1: Целое число N.
 
* Строки 2..1+N: Каждая строка содержит 2 целых числа, указывающих x  и y координаты камня команды A (каждая координата лежит в диапазоне -40,000 .. +40,000).
 
* Строки 2+N..1+2N: Каждая строка содержит 2 целых числа, указывающих x  и y координаты камня команды B (каждая координата лежит в диапазоне -40,000 .. +40,000).
 
OUTPUT FORMAT:
 
* Строка 1: Два разделённых пробелом целых числа, представляющих счета команд A и B 
 
SAMPLE:
 
Ввод Вывод
4
0 0
0 2
2 0
2 2
1 1
1 10
-10 3
10 3 		 1 2
 
INPUT DETAILS:
 
У каждой команды по 4 камня.
Команда A имеет камни (0,0), (0,2), (2,0), (2,2).
Команда B имеет камни (1,1), (1,10), (-10,3), (10,3).
 
 
OUTPUT DETAILS:
 
Команда A захватила камень противника в точке (1,1).
Команда B захватила камни противника в точках (0,2) и (2,2).

Вращающаяся пластина

Задача на реализацию Вычислительная геометрия

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

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

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

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

Формат входных данных
В первой строке входного файла задано число n (3 ≤ n ≤ 2 000) — количество вершин многоугольника. В следующих n строках заданы координаты вершин многоугольника в порядке обхода. В следующей строке задано число m (1 ≤ m ≤ 2 000) — количество точек, которые Вася рассматривает как возможные положения второго гвоздя. В следующих m строках заданы координаты этих точек. Все эти точки находятся снаружи от исходного положения пластины. Все координаты во входном файле целые и не превосходят 106 по модулю.

Формат выходных данных
Выходной файл должен содержать m строк. В i-й строке выведите два вещественных числа αi и βi , где αi — максимальный угол в градусах, на который можно повернуть пластину по часовой стрелке, если Вася забьет гвоздь в i-ю точку, а βi — максимальный угол в градусах ,на который в этом случае можно повернуть пластину против часовой стрелки. Если гвоздь не мешает пластине поворачиваться, выведите αi = βi = 360. Ответ считается верным, если его абсолютная или относительная погрешность относительно правильного не превосходит 10−6 .
 

Ввод Вывод
4
0 0
-3 -3
0 -6
3 -3
3
-8 0
-2 0
2 -1		 360.000000000000 360.000000000000
45.000000000000 225.000000000000
251.565051177078 18.434948822922

Пояснение


На рисунке выше изображен тест из примера. Прямоугольник показывает начальное положение пластины.
Точками показаны позиции, в которые Вася планирует забить гвоздь.
Гвоздь, забитый в первую точку, не мешает пластине поворачиваться.
Гвоздь, забитый во вторую точку, позволяет повернуть пластину на 45 гр.  по часовой стрелке или на 225 гр. против часовой стрелки.

 

Кардиоида

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

Кардиоида-- плоская алгебраическая кривая 4-го порядка, которая описывается фиксированной точкой окружности радиуса , катящейся по неподвижной окружности с таким же радиусом

В прямоугольной декартовой системе координат уравнение кривой имеет вид:

Найдите координаты точки пересечения кардиоиды и отрезка EF, если известно:
- коэффициент кардиоиды a;
- координаты вершин отрезка EF;
гарантируеся, что одна из вершин отрезка лежит внутри кардиоиды, а другая снаружи.
Рассмотрим функцию F(x,y,a)= (x2+y2+2ax)2-4a2(x2+y2). Если для точки M с координатами (x,y) F(x,y,a)<0, то точка M лежит внутри кардиоды с параметром a. Если значение функции будет положительным, то точка M лежит снаружи.

Входные данные:
-в 1-й строке вводится вещественное число - значениe коэффициента кардиоды a (по модулю не более 10)
-в 2-й строке вводятся целые значения Ex, Ey, Fx, Fy – координаты вершин отрезка  EF (числа в интервале [-1000;1000]).
Выходные данные:
1 строка  - абцисса точки пересечения (координата x), с точностью не менее 10-5 
2 строка  - ордината точки пересечения (координата y), с точностью не менее 10-5 

Пример:
Входные данные Выходные данные
1.0
-1 1 1 3		 0
2
-2.5
10 4 1 1		 8.91545419
3.63848473

Поиск вершины по ортоцентру (H)

Бинарный поиск Элементарная геометрия Вычислительная геометрия

Точка H – центр пересечения высот треугольника (ортоцентр) АВС.
Найдите абсциссу вершины C (координату x), если известно:
- координаты точек A и B;
- координата точки D, лежащей на прямой ВС;
- точка H лежит на прямой ED (координаты точки E известны);
- для координат выполняются условия: Ax<Cx<Bx;
Входные данные: в 1-й строке вводятся значения Ax, Ay, Bx, By Dx,Dy, Ex, Ey – координаты точек A, B, D, E
Все значения целые числа в интервале [-1000;1000].
Выходные данные: ответ на задание с точностью не менее 10-5.
Пример:

Входные данные Выходные данные
1 1 6 3 9 1 1 5 2.454545
1 2 5 1 6 -1 1 5 3.196078

Прямоугольники

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

Петя нарисовал на клетчатом листке бумаги красивый рисунок прямоугольной формы. Его младшему брату Васе тоже захотелось порисовать, поэтому он вырезал из того же листка бумаги другой прямоугольник. При этом он не делал лишних разрезов, то есть в результате в листке осталась прямоугольная дырка. Кроме того, линии разреза не проходили (даже частично) по границам рисунка Пети. Более того, по границам рисунка не проходили даже продолжения линий разреза.

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

Формат входных данных
Вам даны 8 целых чисел - \(x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4\), где \((x_1, y_1)\) - координаты левого нижнего угла рисунка Пети, \((x_2, y_2)\) - координаты правого верхнего угла рисунка. Аналогично, \((x_3, y_3)\) - координаты левого нижнего угла вырезанного Васей прямоугольника, \((x_4, y_4)\) - координаты правого верхнего угла вырезанного прямоугольника. Гарантируется, что данные прямоугольники невырождены (\(x_1 < x_2\), \(y_1 < y_2\) и аналогичные неравенства для второго набора координат). Листок был не очень большим, поэтому каждое число по модулю не превосходит \(10^4\).

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

Примечание

Лестницу в треугольник

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

На плоскости дана геометрическая фигура "лестница". Она имеет N ступенек, которые заданы положительными координатами. Каждая ступень имеет свою высоту и ширину. Требуется найти прямую, которая отсекает от некоторых ступеней "лестницы" треугольники так, что из полученных фигур можно сложить прямоугольный треугольник такой же площади, что и исходная фигура. Разрешается, чтобы отсекаемые от ступеней треугольники соприкасались только вершинами (но не сторонами).

Формат входных данных:
В первой строке дано число 0 <= N <= 1000. Далее записаны N строк. Каждая строка содержит два целых чисел через пробел 0 < xi, yi < 106 - координаты вершины i-й ступени (ступени перечисляются в порядке сверху вниз, слева направо).

Формат выходных данных:
Ответ содержит одну строку: два числа через пробел - высота и ширина получившегося прямоугольного треугольника. Если существует несколько решений, то вывести любое. Результат выводится с точностью до четырех десятичных знаков после запятой. В случае, когда решение отсутствует, вывести два ноля через пробел

Примечание

Дуга на сфере

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

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

Входные данные
В первой строке находится число R, во второй строке заданы широта и долгота первой точки, в третьей строке - широта и долгота второй точки. Широта в градусах от -90 до 90, долгота в градусах от -180 до 180, 100 <= R <= 10 000, все числа вещественные.

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

Центр тяжести

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

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

Ограничения: число вершин 3 <= N <= 100 000, координаты вершин в декартовой системе координат целые и по модулю не превосходят 20 000.

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

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

Пирамиды

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

Рассматриваемые пирамиды имеют треугольник в основании, то есть являются тетраэдрами. Требуется по заданным длинам рёбер пирамиды найти её объём.

Ограничения: длины рёбер - целые положительные числа, не превосходящие 1000.


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

В первой строке находятся 6 чисел через пробел - длины рёбер пирамиды ABCD. Порядок рёбер: AB, AC, AD, BC, BD, CD.


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

Вывести одно вещественное число с четырьмя знаками после запятой - объём пирамиды.
Hallowen