0149. Вписанные и описанные окружности

Имя входного файла:	circles.in
Имя выходного файла:	circles.out
Ограничение по времени:	1 s
Ограничение по памяти:	32 megabytes

Если все стороны многоугольника касаются окружности, то окружность называется вписанной в многоугольник, а многоугольник - описанным около этой окружности. Если все вершины многоугольника лежат на окружности , то окружность называется описанной около многоугольника, а многоугольник - вписанным в эту окружность.

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

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

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

В первой строке входного файла находятся одно число N (3 ≤ N ≤ 4) - число вершин выпуклого N-угольника. В последующих строках через пробел перечислены координаты вершин: абсцисса и ордината, в порядке обхода. Все координаты - целые числа, по модулю не превосходящие 10⁶.

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

Если в N-угольник можно вписать окружность, то в первой строке нужно вывести "r=" и ее радиус с точностью 3 знака после запятой. Если около N-угольника можно описать окружность, то либо в первой строке, если не существует вписанной окружности, либо во второй вывести "R=" и радиус с точностью 3 знака после запятой. Если же ни вписанной, ни описанной окружности не существует, выведите "No solutions".

Пример:

circles.in	circles.out
3 0 0 0 1 1 0	r=0.293 R=0.707

Источник: Petrozavodsk Summer 2003. Petrozavodsk SU Contest #2, Friday, August 29

Обсудить       Отправить решение



Версия для печати