Problem A. Smooth convex hull

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

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. Астероидное поле

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

Условие

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

Каждый астероид имеет форму круга и задается координатами центра 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

Author:Far-Eastern Subregional
Input file: input.txt   Time limit:3 sec
Output file: output.txt   Memory limit:8 Mb

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. Треугольники

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

Условие

Будем различать следующие варианты взаимного расположения двух треугольников в пространстве:

  1. треугольники не пересекаются;
  2. угол первого треугольника "протыкает" второй треугольник;
  3. угол второго треугольника "протыкает" первый треугольник;
  4. контуры треугольников сцеплены между собой.
Напишите программу, определяющую вариант расположения двух треугольников, заданных координатами своих вершин.

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

В первой строке входного файла содержится девять чисел 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

0.045s 0.006s 17