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