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

Задачи из рубрикатора

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

Условие задачи  
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