Problem A. Smooth convex hull
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
|
Задача B. Астероидное поле
Условие
В плоской галактике с недавнего времени образовалось слишком много астероидов
и они стали мешать транспортным кораблям передвигаться.
Их приходится облетать, а на изменение курса требуется очень много топлива.
Вам предлагается написать программу, которая по заданной плоской астронавигационной
карте с известными координатами астероидов и положением транспортного корабля
определит какой-либо прямой курс, на котором кораблю не встретится ни одного астероида
Каждый астероид имеет форму круга и задается координатами центра 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
|
Problem C. Circular Area
Statement
Your task is to write a program, which, given two circles,
calculates the area of their intersection with the accuracy of two
digits after decimal point.
Input file format
In the single line of input file there are space-separated real numbers
x1 y1 r1 x2 y2 r2.
They represent center coordinates and radii of two circles.
Output file format
The output file must contain single real number — the area.
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
20.0 30.0 15.0 40.0 30.0 30.0
|
608.37
|
Задача D. Треугольники
Условие
Будем различать следующие варианты
взаимного расположения двух треугольников в пространстве:
- треугольники не пересекаются;
- угол первого треугольника "протыкает" второй треугольник;
- угол второго треугольника "протыкает" первый треугольник;
- контуры треугольников сцеплены между собой.
Напишите программу, определяющую вариант расположения двух треугольников,
заданных координатами своих вершин.
Формат входного файла
В первой строке входного файла содержится девять чисел
x1, y1, z1, x2, y2, z2, x3, y3, z3,
разделенных пробелами — координаты вершин первого треугольника.
В второй строке входного файла содержится девять чисел
x4, y4, z4, x5, y5, z5, x6, y6, z6,
разделенных пробелами — координаты вершин второго треугольника.
Формат выходного файла
В первой строке выходного файла вывести одно целое число — номер варианта взаимного расположения треугольников.
Ограничения
Все числа целые, не превышающие по абсолютному значению 1000.
Расположение треугольников таково, что варианты хорошо различимы,
т.е. либо треугольники находятся на некотором расстоянии друг от друга,
либо отрезок, являющийся пересечением треугольников, имеет ненулевую длину.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
0 0 0 10 0 0 0 10 0
1 1 -1 10 10 -1 1 1 10
|
3
|
