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


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


Условие задачи Прогресс
ID 21772. Перевод часов
Темы: Вычислительная геометрия   

В плоской стране наступила очередная зима, и нужно срочно переводиться на зимнее время! Проблема в том, что стрелка городских часов (единственная, кстати), находящихся в начале координат, очень-очень тяжёлая, и поэтому рабочие хотят узнать, в какую сторону крутить стрелку будет быстрее. Чтобы упростить вам задачу, они уже посчитали, куда указывает стрелка и куда она должна указывать. Помогите им!
 
Входные данные
В первой строке задаётся точка, куда указывает стрелка. Она задаётся координатами 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

ID 21773. Ленивый Вася и релиз 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

ID 21771. Пикап-мастер
Темы: Вычислительная геометрия   

Недавно Венцеслав прочитал новую книгу по пикапу, и теперь он хочет опробовать свои знания в парке. Для простоты представим парк в виде набора тропинок, которые являются отрезками на плоскости. Венцеслав уже гулял в этом парке, и знает, какая девушка по какой тропинке гуляет. Проблема в том, что Венцеслав очень ленивый, и гуляет только по одной тропинке. А ещё ему лень узнать, каких девушек он может встретить по пути, и поэтому он попросил Вас, своего лучшего друга, помочь ему в этом непростом деле.
 
Входные данные
В первой строке вводятся координаты концов тропинки (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

 

ID 27074. Площадь треугольника
Темы: Вычислительная геометрия   

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

ID 27075. Принадлежность точки лучу
Темы: Вычислительная геометрия   

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

 

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

ID 27078. Сумма штрафа
Темы: Вычислительная геометрия   

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

 

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

ID 27077. В каком ухе жужжит?
Темы: Вычислительная геометрия   

Фрекен Бок находится в точке \(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

ID 18377. Полярный угол точки
Темы: Вычислительная геометрия   

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

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

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

 

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

ID 38445. Зеркала
Темы: Вычислительная геометрия   

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

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

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

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

ID 39757. Треугольник. Поиск вершины по положению центроида
Темы: Бинарный поиск    Элементарная геометрия    Вычислительная геометрия   

Точка G – центр пересечения медиан треугольника (центроид) АВС.
Найдите абсциссу вершины C (координату x), если известно:
- координаты точек A и B;

- координата точки D, лежащей на прямой ВС;
- точка G лежит на прямой ED (координаты точки E известны);
- для координат выполняются условия: Ax<Cx<Bx;
Входные данные: в 1-й строке вводятся значения Ax, Ay, Bx, By Dx,Dy, Ex, Ey – координаты точек A, B, D

Все значения целые числа в интервале [-1000;1000].

Выходные данные: ответ на задание с точностью не менее 10-5.
Пример:

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

ID 39774. Поиск вершины по ортоцентру (H)
Темы: Бинарный поиск    Элементарная геометрия    Вычислительная геометрия   

Точка H – центр пересечения высот треугольника (ортоцентр) АВС.
Найдите абсциссу вершины C (координату x), если известно:
- координаты точек A и B;
- координата точки D, лежащей на прямой ВС;
- точка лежит на прямой 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

ID 39795. Поиск вершины по центру описанной окружности (O)
Темы: Бинарный поиск    Элементарная геометрия    Вычислительная геометрия   

Точка O – центр описанной окружности треугольника АВС.
Найдите абсциссу вершины C (координату x), если известно:
- координаты точек A и B;
- координата точки D, лежащей на прямой ВС;
- точка лежит на прямой 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

ID 39818. Поиск вершины по центру вписанной окружности (I, инцентр)
Темы: Бинарный поиск    Элементарная геометрия    Вычислительная геометрия   

Точка I – центр вписанной окружности треугольника АВС (инцентр).
Найдите абсциссу вершины C (координату x), если известно:
- координаты точек A и B;
- координата точки D, лежащей на прямой ВС;
- точка лежит на прямой 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