Темы --> Информатика --> Алгоритмы --> Вычислительная геометрия
    Градиентный спуск(1 задач)
    Элементарная геометрия(144 задач)
    Многоугольники. Выпуклые оболочки(38 задач)
    Клеточная геометрия(8 задач)
    Квадродерево(3 задач)
---> 11 задач <---
Источники --> Командные олимпиады --> Московская командная олимпиада
    8 класс(18 задач)
    9-11 классы(228 задач)
Страница: 1 2 3 >> Отображать по:
#34
Разрезанный прямоугольник
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

 4
Рисунок, соответствующий 1-му примеру входных и выходных данных

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

Сначала на вход программы поступают два положительных числа X и Y, задающих координаты правого верхнего угла прямоугольника. Прямоугольник расположен в системе координат так, что левый нижний его угол имеет координаты 0,0 и стороны параллельны осям координат.

Далее вводится целое число N — количество разрезов (1≤N≤200). Затем описываются сами разрезы. Каждый разрез делался вдоль некоторой прямой. Каждая прямая, соответствующая разрезу, задается тремя числами A, B, C такими, что все точки (x,y) этой прямой (и только они) удовлетворяют уравнению Ax+By+C=0 (при этом всегда A2+B2>0).

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

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

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

Система оценки

1 балл получат программы, правильно решающие задачу при ограничении 1≤N≤50.

Примеры
Входные данные
5.00 1.00
3
1.00 -2.00 0.00
1.00 -3.00 -2.00
1.00 1.00 -4.00
Выходные данные
3
Входные данные
4.00 2.00
2
1.00 -2.00 0.00
1.00 2.00 -4.00
Выходные данные
4
#43
Лапта
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке входных данных содержатся два числа: D — максимальное расстояние удара и N — количество соперников на поле (D и N натуральные числа, D ≤ 1000, N ≤ 200). В следующих N строках задается по три числа – начальные координаты xi и yi и максимальная скорость vi соответствующего игрока (скорости и координаты — целые числа, –1000 ≤ xi ≤ 1000, 0 ≤ yi ≤ 1000, 0 < vi ≤ 1000), никакие два игрока не находятся изначально в одной точке. Игрок, бьющий мяч, находится в точке с координатами (0,0). Мяч выбивается в точку с неотрицательной ординатой (y ≥  0).

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

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

Оценка задачи

1 балл получат программы, которые верно работают, когда в поле не более двух соперников.

Примеры
Входные данные
10 2
1 1 1
-1 1 1
Выходные данные
9.05539
0.00000 10.00000
#860
Путь через горы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Поверхность Земли в горной местности можно представить в виде ломаной линии. Вершины ломаной расположены в точках (x1, y1), (x2, y2),…,(xN, yN), при этом xi<xi+1.

Обычный горный маг находится в точке (x1, y1) и хочет попасть в точку (xN, yN). При этом он может перемещаться только пешком. Он может ходить по поверхности Земли (т.е. вдоль ломаной). А может сотворить в воздухе мост и пройти по нему. Мост может соединять две вершины ломаной: мост не может начинаться и заканчиваться не в вершине ломаной, и мост не может проходить под землей (в том числе не может быть туннелем в горе), но мост может каким-то своим участком проходить по поверхности земли. Длина моста не может быть больше R. Суммарно маг может построить не более K мостов.

Какое наименьшее расстояние придется пройти магу, чтобы оказаться в точке (xN, yN).

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

Вводится сначала натуральное число N (2≤N≤100). Затем водится натуральное число K (1≤K≤100) — максимальное количество мостов. Далее вводится целое число R (0≤R≤10000) — максимальная возможная длина моста. Далее вводятся координаты (x1, y1), (x2, y2),…,(xN, yN). Все координаты – целые числа, не превышающие по модулю 10000, для всех i от 1 до N–1: xi<xi+1.

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

Выведите одно число — минимальную длину пути, которую придется пройти магу (как по земле, так и по мостам). Ответ выведите не менее чем с 5 цифрами после десятичной точки.

Примеры

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

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

5 2 5

0 0

2 2

3 -1

4 1

5 0

6.47871

9 2 3

1 2

2 1

3 3

5 -1

6 2

7 0

8 1

9 0

10 1

14.93498
#1189
Посчитайте лампы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

На новой станции метро, которую планируют открыть в конце этого года, будет 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.

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

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

Примеры
Входные данные
2 20 4 5 1
Выходные данные
0
Входные данные
4 20 4 5 2
Выходные данные
11
#1234
ООО
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Одна серьезная организация (ОСО) решила построить очень охраняемый объект (ООО). Для этого она нашла на пустыре два одиноко стоящих прожектора. Каждый из прожекторов освещает какой-то угол, меньший 180 градусов. ОСО хочет, чтобы весь ООО был освещен обоими прожекторами.

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

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

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

Во входном файле последовательно заданы описания двух прожекторов. Каждый из прожекторов описывается следующим образом: сначала идут координаты прожектора, а затем — координаты двух точек: по одной точке на каждой из сторон угла, освещаемого им. Все числа целые, не превосходящие по модулю 10000.

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

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

Примеры
Входные данные
0 1 2 3 3 2
3 0 3 3 5 2
Выходные данные
-1
Входные данные
0 1 2 3 3 2
3 0 3 3 -3 2
Выходные данные
3.000000
Входные данные
0 1 2 3 3 2
3 0 3 -2 -3 2
Выходные данные
0.000000
Страница: 1 2 3 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест