Темы --> Информатика --> Алгоритмы --> Вычислительная геометрия --> Элементарная геометрия
---> 31 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
#1046
Пересечение кубов
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

В пространстве с прямоугольной системой координат находятся два куба. Про них известно следующее:

  • сторона каждого куба равна 2,
  • центр (т.е. центр симметрии) каждого куба совпадает с началом данной системы координат,
  • координаты вершин >первого куба A1A2A3A4A5A6A7A8 следующие: A1(1, 1, 1), A2(1, –1, 1), A3(–1, –1, 1), A4(–1, 1, 1), A5(1, 1, –1), A6(1, –1, –1), A7(–1, –1, –1), A8(–1, 1, –1),
  • вершины второго куба B1B2B3B4B5B6B7B8 пронумерованы так, что путем поворота кубы можно совместить, и при этом совместятся соответствующие их вершины (A1 и B1, A2 и B2, … , A8 и B8)
  • координаты вершин второго куба даны во входном файле.

Требуется найти объем пересечения (т.е. общей части) этих кубов.

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

Во входном файле записаны 8 троек действительных чисел – координаты вершин второго куба B1B2B3B4B5B6B7B8.

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

В выходной файл выведите одно число – искомый объем пересечения кубов. Ответ не должен отличаться от верного более чем на 0.00001.

Примеры
Входные данные
1.0000000000 -1.0000000000 1.0000000000 
1.0000000000 -1.0000000000 -1.0000000000 
-1.0000000000 -1.0000000000 -1.0000000000 
-1.0000000000 -1.0000000000 1.0000000000 
1.0000000000 1.0000000000 1.0000000000 
1.0000000000 1.0000000000 -1.0000000000 
-1.0000000000 1.0000000000 -1.0000000000 
-1.0000000000 1.0000000000 1.0000000000
Выходные данные
8.00000000000000000000
Входные данные
1.4142135623730950488016887242097 0 1
0 -1.4142135623730950488016887242097 1
-1.4142135623730950488016887242097 0 1
0 1.4142135623730950488016887242097 1
1.4142135623730950488016887242097 0 -1
0 -1.4142135623730950488016887242097 -1
-1.4142135623730950488016887242097 0 -1
0 1.4142135623730950488016887242097 -1
Выходные данные
6.62741699796952078000
#1049
Горнолыжные соревнования
  
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes

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

Маршрут должен представлять собой ломаную, начинающуюся в точке старта на вершине горы и заканчивающуюся в точке финиша у ее подножия. Маршрут выбирается таким образом, что y-координата каждой следующей вершины ломаной оказывается строго меньше y-координаты предыдущей вершины. Один из возможных маршрутов представлен на рисунке.

За каждые ворота, через которые не проходит маршрут, лыжнику начисляются штрафные очки. Общий штраф за спуск по маршруту вычисляется как сумма длины маршрута и штрафных очков за непройденные ворота.

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

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

В первой строке входного файла задано число N - количество ворот на трассе (0 ≤ N ≤ 500), в следующих двух строках заданы Sx, Sy, Fx, Fy - координаты точек старта и финиша соответственно. В каждой из следующих N строк записаны четыре числа ai, bi, yi, ci - x-координаты левого и правого концов ворот, y-координата ворот и штраф за непрохождение данных ворот (ai < bi, Fy < yi < Sy, ci - целое число, 0 ≤ ci ≤ 10000). Все координаты - целые числа, не превосходящие по модулю 10000.

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

В выходной файл выведите наименьший возможный общий штраф за прохождение трассы с точностью не менее 4 знаков после десятичной точки.

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

Потестовая.

Примеры
Входные данные
4
3 6
3 1
5 7 4 1
4 5 5 10
1 2 4 5
2 5 2 0
Выходные данные
7.8126
#1100
Муха
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Муха летит вдоль прямой. Если нанести на эту прямую координаты, то можно сказать, что в 0-й момент времени муха пролетает точку с координатой 0 и летит в положительном направлении со скоростью V. Муха может менять свою скорость, однако ускорение мухи не может по модулю превышать величины A, в частности, муха не может мгновенно остановиться. Максимальная скорость мухи не может превышать по модулю величины W.

Известно, что в момент времени T по прямой ударит мухобойка, которая полностью накроет отрезок от точки C до точки D. Если муха в этот момент окажется на этом отрезке, она погибнет.

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

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

Во входном файле заданы числа V, W, A, T, C, D. Все числа целые. 0≤V≤W≤1000, 0≤A≤1000, 0<T≤1000, –1000000≤C≤D≤1000000.

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

Если муха может спастись, выведите, как она должна для этого лететь. Для этого выведите последовательность команд для мухи. Количество команд не должно превышать 100. Каждая команда задается двумя числами Ti, Ai, которые обозначают, что в течение времени Ti муха должна лететь с ускорением Ai. Ti и Ai не обязаны быть целыми, Ti должны быть положительны (не могут быть равны 0), сумма всех Ti должна быть равна T с точностью до 10-6.

Если, в рамках указанных ограничений, муха спастись не сможет, в выходной файл выведите одно число ­–1 (минус 1).

Примечания

Муха может сначала снизить скорость до 0, а затем полететь в обратную сторону (см. примеры).

Если в момент времени T муха окажется на концах отрезка, т.е. в точке C или D, она все равно погибнет.

Комментарии к примерам тестов

1. Муха не сможет спастись.

2. Сначала в течение времени 0.2 муха летит с постоянной скоростью 10, а затем ускоряется с ускорением 4

3. Муха сначала тормозит с ускорением -5, а затем с этим же ускорением начинает лететь в обратную сторону. Набрав скорость 10, муха продолжает лететь с ней без ускорения.

Примеры
Входные данные
10 10 5
1 -100 100
Выходные данные
-1
Входные данные
10 20 5
1 9 11
Выходные данные
1 5
Входные данные
10 10 5
5 0 1000
Выходные данные
4.000000000000000000 -5
1.000000000000000000 0
#1102
Найдите прямую
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На плоскости дано N горизонтальных отрезков. Будем говорить, что прямая пересекает отрезок, если у этой прямой и этого отрезка есть хотя бы одна общая точка (в том числе прямая пересекает отрезок, если она проходит через один из его концов). Требуется найти прямую, пересекающую все отрезки, или установить, что такой нет.>

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

В первой строке входного файла находится единственное число N. В каждой из следующих N строк содержатся по три целых числа Pi, Qi, Ri, описывающих отрезки: соответствующий отрезок соединяет точки (Pi, Ri) и (Qi, Ri). Никакие два отрезка не лежат на одной прямой.

1≤N≤10000, Pi<Qi, все числа по модулю не превосходят 10000.

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

В случае, если искомая прямая существует, выведите в выходной файл коэффициенты ее уравнения (будем задавать прямую уравнением вида A∙x+B∙y+C=0, где x, y – координаты точек прямой, A, B, C – такие коэффициенты, что указанному уравнению удовлетворяют все точки прямой, и только они; соответственно, чтобы задать прямую, нужно задать три числа – A, B, C).

Коэффициенты уравнения должны быть целыми и не должны превосходить по модулю 109 (гарантируется, что при наличии решения такие A, B, C существуют).

Если прямой не существует, выведите в выходной файл сообщение “No solution” (без кавычек).

Примеры
Входные данные
3
0 1 0
0 1 1
0 1 2
Выходные данные
1 0 0
Входные данные
5
0 2 0
2 4 1
1 3 2
1 3 -1
1 3 -2
Выходные данные
3 -1 -5
Входные данные
3
0 1 0
1 2 1
-2 -1 2
Выходные данные
No solution
#1154
Скользящая симметрия
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Движением плоскости называют такое преобразование плоскости, которое сохраняет попарные расстояния между точками, то есть если A1 и B1 – образы некоторых точек A и B при движении, то |A1B1| = |AB|.

Одной из разновидностей движения плоскости является скользящая симметрия. Скользящей симметрией называют композицию симметрии относительно некоторой прямой l и переноса на вектор, параллельный l (этот вектор может быть нулевым). На рисунке показан пример применения скользящей симметрии к отрезку.

 

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

Требуется по координатам двух различных точек A и B и двух точек A1 и B1, находящихся на таком же расстоянии друг от друга, как и точки A и B, найти скользящую симметрию, переводящую точку A в точку A1, а точку B в точку B1.

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

В первой строке входного файла находятся четыре целых числа – координаты двух различных точек A и В. Во второй строке также находятся четыре целых числа – координаты двух различных точек A1 и В1. Гарантируется, что |A1B1| = |AB|. Все числа во входном файле по модулю не превышают 1000. Числа в строках разделены пробелом.

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

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

В первой строке должны выводиться координаты двух различных точек, лежащих на прямой l, относительно которой выполняется симметрия, а во второй – координаты вектора, параллельного этой прямой, на который осуществляется перенос. Вещественные числа должны быть представлены не менее чем с 6 знаками после десятичной точки.

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