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

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

Условие

По горизонтальной плоской поверхности катятся два шарика радиуса 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

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

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

Условие

Два радара, расположенные в точках с координатами (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

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

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

Условие

Для заданных трёх точек 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

Problem D. Area 51

Author:NEERC 2005   Time limit:2 sec
Input file:area.in   Memory limit:256 Mb
Output file:area.out  

Statement

Michael and Nick are living near the famous top-secret Area 51 facility. The facility is enclosed by a fence and is so large that for the purpose of this problem we consider the fence being a line that stretches infinitely into both directions.

Only extremely brave boys are not scared to go to the fence and peek at the facility. Nick is among the brave ones. He once came to the fence and saw a number of chimneys with distinct shapes. As a proof of his bravery he tells everybody what chimneys he saw from his left to his right.

Michael’s father is working at Area51”and has a facility’s map at his home. Michael found this map and he can now verify Nick's claim of being near the facility's fence. However, it turns out to be complicated, and your task is to write a program to perform this verification.

On a map distinctly shaped chimneys are denoted by capital letters from A to Z. Each letter denotes a distinct shape, but chimneys with this shape can appear more than once on a map. The map uses Cartesian coordinate system oriented so that the fence is Ox axis and all chimneys are located on a half-plane with a positive y coordinate. All chimneys are considered to be points (their sizes and actual geometrical shapes are ignored for the purpose of this problem).

Nick claims that he looked from a point on the fence where no two chimneys were on the same line of his sight (a line that originates from his point of view). It means that at the point he looked from, all the chimneys he saw had a well-defined order from left to right.

Michael have already made a preliminary verification of Nick's claim. He made sure that the number of distinctly shaped chimneys matches their number on the map. Now Michael needs to perform a final verification to get a list of x coordinates on a fence (if any) where the corresponding arrangement of chimneys could be seen from. This information shall be presented as an ordered list of open intervals (a1, b1), (a2, b2), …, (an, bn), so that a1 < b1 ≤ a2 < b2 ≤ … ≤ an < bn. Asterisk symbol ("*") is used in place of a1 and/or bn to denote interval that extends to infinity on the left or on the right correspondingly. Note, that bi = ai + 1 = x in case where Nick could not have been at the point x on a fence, because he would have seen more than one chimney on a single line of his sight, but being to the left or to the right of x yields the order of chimneys that he saw.

The picture below shows that if the boy looks from the point x =  − 7 he sees the chimneys in the following order: C, D, D, C. It is so for any point from the set ( − ∞, − 11) ∪ ( − 11, − 3.5) ∪ (14, + ∞) — the first example from the problem statement.

Input file format

The first line of the input file contains an integer number m the number of chimneys at the "Area 51" facility. The second line of the input file contains a string of m letters from A to Z that describe the chimneys that Nick saw from his left to his right. A single letter can be used more than once (if Nick saw the same shape more than once). Then follow m lines that describe chimneys on the map. Each line contains three tokens separated by spaces — chimney shape letter (from A to Z), and two integers xi and yi — chimney coordinates. On these m lines letters appear in arbitrary order, but each letter from A to Z appears the same number of times as on the second line of the input file. No two chimneys have the same coordinates.

Output file format

Write to the first line of the output file a single integer number n — the number of intervals that describe x coordinates on a fence where Nick could have seen the corresponding arrangement of chimneys from. Write to the second line of the output file 2 n numbers a1, b1, …, an, bn using "*" instead of a number a1 and/or bn to denote infinity. Numbers must be precise up to 10 − 6.

Constraints

1 ≤ m ≤ 100,  − 100 ≤ xi ≤ 100, 0 < yi ≤ 100

Sample tests

No. Input file (area.in) Output file (area.out)
1
4
CDDC
C 0 7
D 4 5
C -2 1
D -2 3
3
* -11 -11 -3.5 14 *
2
4
DCCD
C 0 7
D 4 5
C -2 1
D -2 3
2
-3.5 -2.333333 -2.333333 -2
3
4
DCDC
C 0 7
D 4 5
C -2 1
D -2 3
0

Problem E. Smooth convex hull

Author:T. Chistyakov, A. Klenin   Time limit:3 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

There are N points on a plane. Convex hull is such a convex polygon with the least possible area, that all the given points are either within its interior or belong to its border.

Let's say that one convex polygon is smoother that the other one if it's sharpest angle is more obtuse than the sharpest angle of the other one.

Your task is to make the convex hull of the given set of points as smooth as possible. To do it you are allowed to exclude no more than one point from the given set.

Input file format

Input file contains integer N, then N pairs of real numbers xi yi describing given points. There are no duplicate points in the input file.

Output file format

Output file must contain a single number: the sharpest angle (in radians) in the most smooth convex hull with absolute error less than 0.01.

Constraints

3 ≤ N ≤ 1000

1 ≤ xi, yi ≤ 106

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5
1 1  2 10  1 3  3 1  3 3 
1.57
2
4
1 1  1 3  3 1  3 3 
1.57

Problem F. Half of a convex polygon

Author:T. Chistyakov, A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:24 Mb
Output file:output.txt  

Statement

You need to divide a non-degenerate convex polygon with a horizontal line into two parts of equal area.

The polygon is specified by N vertices in the clockwise order.

Input file format

Input file contains integer N, then N pairs of floating-point numbers xi yi describing the vertices of the polygon.

Output file format

Output a single number — the ordinate of the horizontal line dividing the polygon as requested. The result must be rounded to 10-2.

Constraints

3 ≤ N ≤ 1000000

1 ≤ xi, yi ≤ 1000000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4
1 1  1 3  3 3  3 1
2

Задача G. Сухой фотограф

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

Условие

В некотором городе имеется достопримечательность - прямоугольная площадь размером X на Y метров, на которой работают N фонтанов. Турист желает посетить эту площадь и сделать несколько фотографий. Однако если при фотографировании находиться от какого-либо из фонтанов на расстоянии меньше R метров, фотоаппарат может быть поврежден брызгами воды. Помогите фотографу найти безопасную точку съёмки. Требуется по координатам фонтанов определить точку на площади, удалённую от каждого из них не менее чем на R метров, или определить, что такой точки не существует. Если таких точек более одной, вывести любую из них. Обратите внимание, что стоять в точности на границе окружности или прямоугольника разрешено.

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

В первой строке входного файла содержатся числа X Y N R, в каждой из следующих N строк - координаты xi yi i-го фонтана. Числа X Y R во входном файле — вещественные.

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

В выходном файле должны, содержаться два вещественных числа - координаты сухой точки. Если такой точки не существует, следует вывести значения -1 -1. Проверка результатов будет осуществляться путём подстановки координат точки в неравенства, задающие внутренность каждого круга. Эти вычисления будут производиться с использованием вещественных чисел двойной точности (double).

Ограничения

1 <= N <= 100, 1 <= X, Y, R <= 106.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
100 100 4 50
0 0
100 0
0 100
100 100
50 50

Задача H. Поворот отрезка

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

Условие

Вершины отрезка AB имеют координаты (Xa; Ya) и (Xb; Yb).

Требуется найти координаты вершин отрезка A *  B *  (X * a; Y * a) и (X * b; Y * b), полученного путём поворота отрезка AB вокруг точки O (Xo; Yo) на β градусов.

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

Входной файл содержит целые числа Xa, Ya, Xb, Yb, Xo, Yo, β

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

Выходной файл должен содержать четыре вещественных числа X * a, Y * a, X * b, Y * b с точностью 10 − 3.

Ограничения

0 ≤ |Xa|, |Ya|, |Xb|, |Yb|, |Xo|, |Yo| ≤ 105

0 ≤ β ≤ 360

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1  2 2  0 0  90
-1.000000000 1.000000000 -2.000000000 2.000000000
2
1 1  2 2
0 0
45
0.000000000 1.414213562 0.000000000 2.828427125
3
7 5
11 11
9 8
180
11.000000000 11.000000000 7.000000000 5.000000000

Задача I. Астероидное поле

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

Условие

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

Каждый астероид имеет форму круга и задается координатами центра xi yi и радиусом ri. Размерами транспортного корабля можно пренебречь, однако если на проложенном курсе корабль коснется астероида — он разобьется.

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

Во входном файле сначала содержаться начальные координаты корабля x0, y0, затем число N — количество астероидов. Далее следуют N троек чисел xi, yi, ri — описание i-го астероида. В начальном положении корабль не соприкасается ни с одним из астероидов.

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

В выходном файле должно содержаться два числа x1, y1 — координаты точки, на которую кораблю следует взять курс, чтобы не врезаться в астероид. Гарантируется, что такая точка существует, если таких точек несколько, выведите любую из них. Координаты x1, y1 должны отличаться от x0, y0. Ответ выведите с точностью до пятого знака после десятичной точки.

Ограничения

0 ≤ N ≤ 100,  − 10000 ≤ xi, yi, zi ≤ 10000, 1 ≤ ri ≤ 10000.
Все координаты — вещественные числа.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
0.0 0.0
2
1.0 1.0 1.0
1.0 -1.0 1.0
-1.0 0.0

Задача J. Точки на n-мерном параллелепипеде

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

Условие

Пусть имеется набор из m точек n-мерного евклидова пространства, заданных своими декартовыми координатами: (x1i, x2i, …, xni), где нижний индекс обозначает номер точки, а верхний — номер координаты.

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

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

В начале входного файла "input.txt" хранятся два натуральных числа: m и n.

Далее следует m строк, содержащих координаты точек исходного множества: (x1i, x2i, …, xni).

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

Выходной файл "output.txt" должен содержать одно из следующих значений:

1 — если такой параллелепипед существует;

0 — в противном случае.

Ограничения

Все входные значения являются целыми десятичными числами.

 − 104 < xki < 104, 0 < n ≤ 10, 0 < m ≤ 5 ⋅ 104

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

Входной файл (input.txt) Выходной файл (output.txt)
1
 6 3
-3056 -5013 -4706
 6423  9875  1023
-3056 -5013  1023
 6423 -5013 -4706
-3056  9875 -4706
 6423 -5013  1023
1
2
 5 2
-3170 -1400
 4950 -1400
-3170  7030
  150  3500
 4950  7030
0

Задача K. Лена и зеркало

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

Условие

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

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

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

Пусть зеркало наклонено так, что в некоторой системе координат его можно задать как прямую, имеющую уравнение y = kx + b. Направление падения солнечных лучей задаётся единичным вектором a.

Требуется найти направление отражения лучей, а именно, требуется найти единичный вектор c.

Примечание. По законам оптики, свет отражается так, что угол падения равен углу отражения (α = β на рисунке).

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

Входной файл содержит три вещественных числа k x1 y1 — угловой коэффициент прямой и координаты вектора a.

Длина вектора a приближённо равна 1.

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

Выходной файл должен содержать два вещественных числа x2 y2 — координаты вектора c.

Длина вектора c должна быть приближённо равна 1.

Координаты вектора c должны быть выведены с точностью до 3-х знаков после запятой.

Ограничения

 − 1000 ≤ k ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
0 0.7071067812 -0.7071067812
0.7071067812 0.7071067812
2
1 1 0
0 1

0.827s 0.014s 41