Элементарная геометрия


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


Условие задачи Прогресс
ID 25963. *Лапта
Темы: Бинарный поиск по ответу    Элементарная геометрия    Квадродерево   

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


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

- в первой строке входных данных содержатся два числа: D — максимальное расстояние удара и N — количество соперников на поле (D и N натуральные числа, \(D <= 1000\)\(N <= 200\)); 
- в следующих N строках задается по три числа – начальные координаты xi и yi и максимальная скорость vi соответствующего игрока (скорости и координаты — целые числа, \(–1000 <= x_i <= 1000\), \(0 <= y_i <= 1000\), \(0 < v_i <= 1000\)).
Никакие два игрока не находятся изначально в одной точке. Игрок, бьющий мяч, находится в точке с координатами (0,0). Мяч выбивается в точку с неотрицательной ординатой (\(y >=  0\)).


Выходные данные: выведите сначала время, которое потребуется игрокам, чтобы добежать до мяча, а затем координаты точки, в которую нужно выбить мяч. Если таких точек несколько, выведите координаты любой из них. Время и координаты нужно вывести с точностью \(10^{–3}\).
 

Примеры
Входные данные Выходные данные
1
10 2
1 1 1
-1 1 1
9.05539
0.00000 10.00000

ID 38137. Забор по часовой стрелке
Темы: Элементарная геометрия   

Фермер Джон решил заменить изгородь вокруг своего пастбища.
Эта новая изгородь описывается строкой символов, каждый из которых "N" (north), "E" (east), "S" (south), или "W" (west). Каждый символ описывает 1 метр изгороди. Например, если строка NESW, это означает, что изгородь начинатся одним метром на север, затем 1 метр на восток, затем 1 метр на юг, и затем 1 метр на запад, возвращаясь в стратовую точку.

Изгородь всегда заканчивается в той же позиции, где стартовала, и это - единственная точка, посещенная более одного раза путем изгороди (а стартовая точка, единственная точка посещённая второй раз - в конце пути). Как следствие, изгородь огораживает один связный регион травяного пастбища, даже если этот регион может иметь довольно странную форму.

Фермер Джон хочет узнать, указанный путь обходится по часовой стреле или против часовой стрелки? По часовой стрелке - огороженный регион находится по правую сторону от изгороди, если идти по пути, определённому строкой. Против часовой стрелки - огороженный регион находится по левую сторону от изгороди, если идти по пути, определённому строкой.

Входные данные: 
Первая строка содержит целое число N (1≤N≤20). Каждая из последующих N строк содержит строку длиной не менее 4 символов и не более 100, описывающую путь изгороди.
Выходные данные: 
Для каждого из N путей, описанных по вводе, выведите строку содержащую "CW" (clockwise - по часовой стрелке) или "CCW" (counterclockwise - против часовой стрелки).
 

Примеры
Входные данные Выходные данные Пояснение
1 2
NESW
WSSSEENWNEESSENNNNWWWS 
CW
CCW
Оба пути   (? символ "пробел") обозначает стартовую точку:

*>*
^ v

<*

  *<*<*<*
  v     ^
*<
     *
v       ^
* *>*>* *
v ^   v ^
* *<* * *
v   ^ v ^
*>*>* *>*

ID 38294. Метеорит
Темы: Элементарная геометрия   

Беда! К городу N приближается метеорит. Людей уже успели эвакуировать, но домам урона не избежать. Ученые уже выяснили, куда упадет метеорит. Вас, как сотрудника страховой компании, попросили выяснить количество домов, которые пострадают при падении метеорита.

Введём на плоскости прямоугольную систему координат. Город представляет собой прямоугольник n × m . Его левый нижний угол расположен в точке с координатами (0, 0) , а правый верхний угол в точке с координатами ( n - 1, m - 1) . В каждой точке с целыми координатами внутри или на границе этого прямоугольника находится дом. Дома в городе N маленькие, поэтому их можно считать точками.

Известно, что метеорит упал в точку ( x , y ) , а радиус его поражения равен r . Таким образом, все дома города на расстоянии не более r от точки падения метеорита получат повреждения. Найдите количество домов, которые получат повреждения.

Входные данные
Первая строка содержит два целых числа n , m ( 1 ≤ n , m ≤ 500 ) — размеры города N.

Вторая строка содержит три целых числа x , y , r ( - 500 ≤ x , y ≤ 500 ; 0 ≤ r ≤ 500 ) — координаты точки падения метеорита и радиус поражения, соответственно.

Выходные данные
Выведите одно число — количество повреждённых домов.

Примечание
Иллюстрация к тесту из примера: чёрными точками обозначены повреждённые дома, белыми — уцелевшие.

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

ID 38297. Сломанный робот
Темы: Элементарная геометрия    Конструктив   

В 2037-м году для создания научно исследовательской базы на Марс высадился отряд роботов, один из которых отправился собирать информацию о районе дислокации. В данный момент роботу из-за отказа некоторых узлов срочно необходимо вернуться в место закладки будущей базы.
Поверхность Марса в районе высадки десанта можно условно представить в виде плоскости с введенной на ней системой координат, такой, что база находится в точке (0, 0). Робот же остановился в точке (x0, y0). Он может перемещаться в четырёх направлениях:
• «R» — вправо, при этом координата x робота увеличивается на 1;
• «L» — влево, при этом координата x робота уменьшается на 1;
• «U» — вверх, при этом координата y робота увеличивается на 1;
• «D» — вниз, при этом координата y робота уменьшается на 1.
Из-за неисправности робот не может совершить два перемещения подряд в одном направлении.
Помогите роботу вернуться на базу. Робот должен сделать не более 10000 передвижений, иначе он разрядится и не доедет до базы!

Входные данные
В единственной строке входных данных находятся два целых числа x0 и y0 — изначальные координаты робота (−1000 ≤ x0, y0 ≤ 1000).

Выходные данные
В первой строке выведите целое число, не большее 10000 — количество операций, которые должен сделать робот. Во второй строке выведите сами операции. Каждая операция задаётся одной буквой:
вправо — «R» влево — «L», вверх — «U», вниз — «D». Символы необходимо выводить без пробелов между ними.
 

Примеры
Входные данные Выходные данные
1 2 1 5
DLULD


Замечание
Вы не обязаны выводить кратчайший маршрут. Например, в приведенном примере кратчайший
маршрут состоит из 3 передвижений: влево, вниз, влево.
Иллюстрация к тесту из примера:

ID 38315. Треугольник
Темы: Элементарная геометрия   

На координатной плоскости расположены равнобедренный прямоугольный треугольник ABC с длиной катета d и точка X. Катеты треугольника лежат на осях координат, а вершины расположены в точках: A (0,0), B (d,0), C (0,d).

Напишите программу, которая определяет взаимное расположение точки X и треугольника. Если точка X расположена внутри или на сторонах треугольника, выведите 0. Если же точка находится вне треугольника, выведите номер ближайшей к ней вершины.

Входные данные
Сначала вводится натуральное число d(не превосходящее 1000), а затем координаты точки X – два целых числа из диапазона от ­–1000 до 1000.

Выходные данные
Если точка лежит внутри, на стороне треугольника или совпадает с одной из вершин, то выведите число 0. Если точка лежит вне треугольника, то выведите номер вершины треугольника, к которой она расположена ближе всего (1 – к вершине A, 2 – к B, 3 – к C). Если точка расположена на одинаковом расстоянии от двух вершин, выведите ту вершину, номер которой меньше.

Примеры
Входные данные Выходные данные Пояснение
1 5
1 1
0 Точка лежит внутри треугольника.
2 3
-1 -1
1 Точка лежит вне треугольника и ближе всего к ней вершина A
3 4
4 4
2 Точка лежит на равном расстоянии от вершин B и C,в этом случае нужно вывести ту вершину, у которой номер меньше, т.е. выведено должно быть число 2
4 4
2 2
0 Точка лежит на стороне треугольника.

ID 38348. Посчитайте лампы
Темы: Элементарная геометрия   

На новой станции метро, которую планируют открыть в конце этого года, будет N эскалаторов (эскалаторы пронумерованы подряд числами от 1 до N). Эскалаторы имеют длину L и расположены на расстоянии H друг от друга. Шириной эскалатором пренебрежем. Между каждыми двумя соседними эскалаторами (точно посередине) будет установлен ряд ламп. В ряду будет K ламп. Лампы устанавливаются по следующему принципу: всю длину эскалатора L разбивают на K равных отрезков и в середине каждого отрезка устанавливают по лампе (см. рисунок). Всего будет установлено (N–1)*K ламп.


На приведенном рисунке N=4 (эскалаторы показаны жирными <горизонтальными линиями), L=20, H=4, K=5.

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

Входные данные
Во входном файле записаны числа N, L, H, K, J. Все числа — натуральные. 2≤N≤35, 1≤L≤1000, 1≤H≤1000, 1≤K≤35, 1≤J≤N.

Выходные данные
В выходной файл выведите одно число — ответ задачи.

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

ID 38361. Дремучий лес
Темы: Элементарная геометрия   

Просека — эта такая прямая линия, которая проходит через лес (то есть деревья есть как с одной стороны от этой линии, так и с другой), и при этом она не проходит ни через одно из деревьев леса, а также не касается деревьев. Будем говорить, что лес является дремучим, если в нем нет ни одной просеки.

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

Входные данные
Во входном файле содержится сначала целое число N — количество деревьев (1 ≤ N ≤ 200). Затем идет N троек чисел, задающих деревья. Первые два числа задают координаты центра, а третье — радиус. Все данные задаются точно, и выражаются вещественными числами, не более чем с 2 знаками после десятичной точки, по модулю не превосходящими 1000.

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

Примеры
Входные данные Выходные данные
1 3
 0.00 30.00 25.00
 0.00 -30.00 25.00
 40.00 0.00 16.00
NO
-833.3333340000 -552.7707973875
 833.3333340000 552.7707973875
2 3
0.00 30.00 29.00
0.00 -30.00 29.00
40.00 0.00 19.00
YES

ID 38387. Клад
Темы: Элементарная геометрия   

Найти закопанный пиратами клад просто: всё, что для этого нужно – это карта. Как известно, пираты обычно рисуют карты от руки и описывают алгоритм нахождения клада так: «Встаньте около одинокой пальмы. Пройдите тридцать шагов в сторону леса, потом семнадцать шагов в сторону озера, …, наконец десять шагов в сторону большого булыжника. Клад находится под ним». Большая часть таких указаний просто сводится к прохождению какого-то количества шагов в одном из восьми направлений (1 – север, 2 – северо-восток, 3 – восток, 4 – юго-восток, 5 – юг, 6 – юго-запад, 7 – запад, 8 – северо-запад) (см. рис). Длина шага в любом направлении равна 1.
    Путешествие по такому пути обычно является прекрасным способом посмотреть окрестности, однако в наше время постоянной спешки ни у кого нет времени на это. Поэтому кладоискатели хотят идти напрямую в точку, где зарыт клад. Например, вместо того, чтобы проходить три шага на север, один шаг на восток, один шаг на север, три шага на восток, два шага на юг и один шаг на запад, можно пройти напрямую, использовав около 3.6 шага (см. рис).


Вам необходимо написать программу, которая по указаниям пиратов определяет точку, где зарыт клад.
 Формат входных данных
    Первая строка  содержит число N – число указаний (1≤N≤40). Последующие N строк содержат сами указания – номер направления (целое число от 1 до 8) и количество шагов (целое число от 1 до 1000). Числа разделены пробелами.
Формат выходных данных
    Выведите координаты X и Y точки (два вещественных числа, разделённые пробелом), где зарыт клад, считая, что ось Ox направлена на восток, а ось Oy – на север. В начале кладоискатель должен стоять в начале координат. Координаты необходимо вывести с погрешностью не более 10-3.
 

Примеры
Входные данные Выходные данные
1 6
1 3
3 1
1 1
3 3
5 2
7 1
3.000 2.000
2 1
8 10
-7.071 7.071

ID 38432. Целые точки
Темы: Элементарная геометрия    НОД и алгоритм Евклида   

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

Формат входных данных
    В первой строке содержится N (3 ≤N ≤1000) – число вершин многоуголь¬ника. В последующих N строках идут координаты (Xi, Yi) вершин многоугольника в порядке обхода по часовой стрелке. Xi и Yi - целые числа, по модулю не превосходящие 1000000.

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

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

ID 38551. Параллелограмм
Темы: Элементарная геометрия   

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

Вася, если честно, не очень понял тему про параллелограммы, и ему требуется программа, умеющая правильно отвечать на Петины вопросы.

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

Входные данные
В первой строке входного файла записано целое число N (1 ≤ N ≤ 10) - количество заданных Петей вопросов. Каждая из N последующих строк содержит описание четырех точек - четыре пары целых чисел X и Y (−100 ≤ X ≤ 100, −100 ≤ Y ≤ 100), обозначающих координаты точки.

Выходные данные
Для каждого из вопросов определите, образуют ли данные точки параллелограмм. Если они образуют параллелограмм, то выведите номера этих точек в одной строке через пробел в порядке обхода параллелограмма. Начинать обход можно с любой из вершин. Если они не образуют параллелограмм, выведите в этой строке одно число 0. Ответ на каждый из запросов должен быть в отдельной строке.
 

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

ID 38652. Уравнение прямой
Темы: Элементарная геометрия   

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

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


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

ID 38657. Уравнение прямой - 2
Темы: Элементарная геометрия   

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

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

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

ID 38658. Принадлежность точки прямой
Темы: Элементарная геометрия   

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

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


Примеры
Входные данные Выходные данные
1 8 7 2 -3 5 YES

ID 38659. Расстояние от точки до прямой
Темы: Элементарная геометрия   

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

Выходные данные
Одно число – расстояние от точки до прямой.
 

Примеры
Входные данные Выходные данные
1 1 5 0 -4 8 3.00000

ID 38660. Расстояние от точки до луча
Темы: Элементарная геометрия   

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

Выходные данные
Одно число – расстояние от точки до луча, определяемого вектором.
 

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

ID 38661. Расстояние от точки до отрезка
Темы: Элементарная геометрия   

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

Выходные данные
Одно число – расстояние от точки до отрезка.
 

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

ID 38662. Пересечение отрезков
Темы: Элементарная геометрия   

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

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

Примеры
Входные данные Выходные данные
1 1 2 1 2
1 2 1 2
YES
2 3 3 5 6
5 6 3 3
YES

ID 38663. Пересечение двух прямых
Темы: Элементарная геометрия   

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

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

Примеры
Входные данные Выходные данные
1 4 -4 0 0 -3 6 2.00000 2.00000

ID 38664. Биссектриса
Темы: Элементарная геометрия   

Входные данные
Шесть чисел – координаты точек X, Y и Z.

Выходные данные
Три числа – коэффициенты уравнения биссектрисы угла YXZ.


Примеры
Входные данные Выходные данные
1 0 0 1 0 0 1 1.000000 -1.000000 0.000000
2 0 0 1 3 1 -3 0.000000 -0.632456 0.000000

ID 38665. Касательная к окружности
Темы: Элементарная геометрия   

Входные данные
Пять чисел – координаты центра и радиус окружности, координаты точки.

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

Примеры
Входные данные Выходные данные
1 2 2 2 2 5 2
0.50929 3.33333
3.49071 3.33333

ID 38669. Окружность и прямая
Темы: Элементарная геометрия   

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

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

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

ID 38672. Две окружности
Темы: Элементарная геометрия   

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

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

Примеры
Входные данные Выходные данные
1 3 4 5 11 4 2 0
2 3 4 5 9 4 2 2
7.75000 5.56125
7.75000 2.43875

ID 38673. Длина дуги
Темы: Элементарная геометрия   

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

Выходные данные
Одно число – длина меньшей дуги окружности, заключённой между указанными точками.
 

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

ID 38689. Сортировка точек
Темы: Структуры    Использование сортировки    Элементарная геометрия   

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

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

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

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

 Примеры

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

ID 44037. Ускорители для Деда Мороза
Темы: Динамическое программирование на таблицах    Элементарная геометрия    Алгоритмы на графах   

Дед Мороз за ночь должен посетить 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....