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

Input file name: circles.in
Output file name: circles.out
Time limit: 1 s
Memory limit: 32 megabytes

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

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

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

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

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

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

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

Пример:

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


Source: Petrozavodsk Summer 2003. Petrozavodsk SU Contest #2, Friday, August 29

Discuss       Submit a solution



Printable version