Задача A. Пеленг НЛО ≡

Автор:А. Кленин
Входной файл:input.txt   Ограничение времени:5 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

Два радара, расположенные в точках с координатами (0, 0) и (100, 0), обнаружили неопознанный объект. По таинственной причине, связанной, возможно, с внеземной природой объекта, радары оказались способны определить только направление на объект (пеленг), но не расстояние до объекта. Пеленг измеряется в градусах, против часовой стрелки, начиная от направления "на восток" (т. е. пеленг второго радара относительно первого равен 0°, пеленг первого радара относительно второго — 180°).

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

Формат входного файла

Во входном файле содержатся вещественные числа a и b, разделенные пробелами.

Формат выходного файла

В выходном файле должны содержаться два вещественных числа, x и y, представляющие координаты объекта с точностью до 4 знаков после запятой. Если определить координаты невозможно, следует вывести два числа 0 (нуль).

Ограничения

0 ≤ a, b ≤ 360

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
45.1 135.0
 
49.9127 50.0873
2 
135.0 45.0
 
0 0

Задача B. Точка Ферма-Торричелли ≡

Автор:StdAlg
Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

Для заданных трёх точек A, B, C найти такую точку O, что AO + BO + CO — минимально.

Формат входного файла

Во входном файле содержатся целые числа XA YA XB YB XC YC — координаты точек A, B, C соответственно.

Формат выходного файла

Выходной файл должен содержать два числа XO YO — координаты точки O с точностью до 3-х знаков после запятой.

Ограничения

0 ≤ |XA|, |YA|, |XB|, |YB|, |XC|, |YC| ≤ 105

Никакие две точки не совпадают

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
4 2 0 0 2 2
 
2 2
2 
-2 -3 1 3 4 -2
 
1.30120904214632 -0.720188590098661

Задача C. Столкновение шариков ≡

Автор:А. Кленин
Входной файл:input.txt   Ограничение времени:4 сек
Выходной файл:output.txt   Ограничение памяти:200 Мб

Условие

По горизонтальной плоской поверхности катятся два шарика радиуса R метров каждый. В начальный момент времени шарики имеют координаты центров (x1, y1) и (x2, y2) метров, а также проекции скоростей на координатные оси (dx1, dy1) и (dx2, dy2) метров в секунду соответственно.

Требуется найти время в секундах, спустя которое шарики столкнутся, или определить, что этого не произойдёт.

Формат входного файла

Входной файл содержит вещественные числа R x1 y1 dx1 dy1 x2 y2 dx2 dy2.

Формат выходного файла

Выходной файл должен содержать вещественное число — время до столкновения, с точностью не менее 3 значащих цифр, либо −1, если столкновения не произойдёт.

Ограничения

1 ≤ R ≤ 1000, −1000 ≤ x1, y1, dx1, dy1, x2, y2, dx2, dy2 ≤ 1000,

(x1 − x2)2 + (y1 − y2)2 > 4 R2

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
1
0 0 10 0
50 0 -10 0
 
2.4

Задача D. Физика Хоттабыча ≡

Автор:А. Жуплев, И. Туфанов
Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

Прожив 1000 лет, Гассан Абдуррахман ибн Хоттаб занялся изучением физики. Законы, описывающие кинетическую и потенциальную энергию, показались ему слишком сложными, и Хоттабыч решил их немного изменить.

Теперь энергия материальной точки в определённый момент времени будет равна E, если в радиусе L метров от неё найдётся ещё хотя бы одна точка, либо P, если таких точек нет.

На бесконечной плоскости имеется K материальных точек. Хоттабыч знает начальное положение каждой точки (xi; yi) и их скорости вдоль осей OX и OY — ui и vi. Таким образом, i-ая точка в момент времени t будет иметь координаты (xi + ui*t; yi + vi*t).

Хоттабыч наблюдал за движением точек ровно T секунд. Теперь он хочет вычислить максимальное значение, которого достигала в течение этого периода сумма энергий всех материальных точек.

Рекомендуется рассмотреть частичные решения

Формат входного файла

В первой строке входного файла содержатся числа K E P L T, причём K, E, P — целые, L, T — действительные, заданные с точностью 0.001

В следующих далее K строках содержатся целые числа xi yi ui vi

Формат выходного файла

В выходном файле должно содержаться единственное целое число — максимальное значение суммы энергий материальных точек, достигнутое на отрезке времени [0; T]

Ограничения

1 ≤ K ≤ 1000

0 ≤ E, P, L, T ≤ 1000

−1000 ≤ xi, yi, ui, vi ≤ 1000

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
1 20 100 0.000 0.000
0 0 0 0
 
100
2 
3 20 15 1.000 531.715
0 0 0 0
1 1 1 0
2 2 0 -1
 
55
3 
4 1000 992 0.001 3.133
10 10 -70  -70 
20 20 -140 -140 
30 30 -210 -210 
40 40 -280 -280
 
4000

Задача E. Поездка на Хэллоуин ≡

Автор:А. Жуплев
Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

Владивостокский программист приглашает коллегу к себе домой в гости на празднование Хэллоуина.

Оба программиста живут за городом. Их дома расположены в точках с координатами (XA; YA) и (XB; YB).

В этом районе есть только одна асфальтированная дорога, представимая в виде отрезка с координатами начала (XS; YS) и конца (XE; YE). Дорога является платной: за любой въезд на дорогу (проезд по произвольному участку дороги или только пересечение — не имеет значения) взимается плата в размере CR. Остальная местность занята полями, которые (в связи со скорым Хэллоуином) сплошь засажены тыквами. При движении на автомобиле по полю взимается плата в размере CF за каждый километр пути — ущерб за раздавленные тыквы.

Помогите программисту добраться к другу с минимальными затратами.

Обратите внимание, при сколь угодно малом приближении к дороге плата за въезд на неё не взимается. Смотрите пример №3.

Формат входного файла

Во входном файле содержатся десять целых чисел: XA YA XB YB XS YS XE YE CF CR

Формат выходного файла

Выходной файл должен содержать единственное число — минимальные затраты при перемещении из A в B с абсолютной ошибкой не более 10−3.

Ограничения

−103 ≤ XA, YA, XB, YB, XS, YS, XE, YE ≤ 103

1 ≤ CF ≤ 103

1 ≤ CR ≤ 106

Дома программистов находятся в разных точках и не находятся на дороге

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
1 1 2 2 0 3 3 0 1 1
 
2.414213562373095
2 
1 5 4 0
-2 -2 10 10
1 2
 
7.656854249492381
3 
10 10 25 19
15 13 20 16
1 1000000
 
17.492855684535900

Problem F. Cosmonaut ≡

Author:I. Ludov
Input file:input.txt   Time limit:2 sec
Output file:output.txt   Memory limit:64 Mb

Statement

In the year 2030 International Space Station 2 was launched. It had a torus shape to enable artificial gravity generation. (A torus is a circular tube with circular cross-section). Advanced spacesuit technology and micro-rocket engines allowed for prolonged and easy spacewalks.

During one such spacewalk a crew member was looking at the station from an open space and wondered where should he fly to get to the station surface as fast as possible. Since he was cosmonaut and not astronaut, he had good mathematics education. So after a return to the station he quickly wrote a program which constructed the shortest line from any given point in space to the surface of a given torus.

Can you do this too?

Input file format

Input file contains eleven integer numbers:

xc yc zc — coordinates of torus center,

xd yd zd — a vector collinear to torus symmetry axis,

r1 — distance from the center of the tube to the center of the torus,

r2 — radius of the tube,

x y z — coordinates of the point in space.

Output file format

Output file must contain real numbers xm ym zm — coordinates of the nearest torus point with at least 15 correct digits after decimal point. If there is more than one nearest point, output any of them.

Constraints

−106 xc, yc, zc, xd, yd, zd, x, y, z ≤ 106,

0 < r2 < r1 ≤ 106, |xd| + |yd| + |zd| > 0,

point (x, y, z) lies either outside the torus or on its surface.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
0 0 0
0 0 1
10 1
1 0 0
 
9.0 0.0 0.0
2 
5 6 7 1 1 1 50 10 3 2 1
 
32.5203582126019 5.16103228678696 -22.1982936390279

Problem G. Box ≡

Author:Michail Mirzayanov
Input file:box.in   Time limit:2 sec
Output file:box.out   Memory limit:64 Mb

Statement

Ivan works at a factory that produces heavy machinery. He has a simple job — he knocks up wooden boxes of different sizes to pack machinery for delivery to the customers. Each box is a rectangular parallelepiped. Ivan uses six rectangular wooden pallets to make a box. Each pallet is used for one side of the box.

Joe delivers pallets for Ivan. Joe is not very smart and often makes mistakes — he brings Ivan pallets that do not fit together to make a box. But Joe does not trust Ivan. It always takes a lot of time to explain Joe that he has made a mistake.

Fortunately, Joe adores everything related to computers and sincerely believes that computers never make mistakes. Ivan has decided to use this for his own advantage. Ivan asks you to write a program that given sizes of six rectangular pallets tells whether it is possible to make a box out of them.

Input file format

Input file consists of six lines. Each line describes one pallet and contains two integer numbers w and h — width and height of the pallet in millimeters respectively.

Output file format

Write a single word `POSSIBLE' to the output file if it is possible to make a box using six given pallets for its sides. Write a single word `IMPOSSIBLE' if it is not possible to do so.

Constraints

1 ≤ w, h ≤ 10000

Sample tests

No. Input file (box.in) Output file (box.out)
1 
1345 2584
2584 683
2584 1345
683 1345
683 1345
2584 683
 
POSSIBLE
2 
1234 4567
1234 4567
4567 4321
4322 4567
4321 1234
4321 1234
 
IMPOSSIBLE
0.120s 0.005s 25