## Balkan OI '11 P1 - Two Circles

View as PDF

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
##### Balkan Olympiad in Informatics: 2011 Day 1, Problem 1

We will consider a convex polygon with vertices. We wish to find the maximum radius such that two circles of radius can be placed entirely inside the polygon without overlapping.

#### Input Specificiation

The first line of input contains the number . Each of the next lines contains a pair of integers , – representing the coordinates of the th point, separated by a space.

#### Output Specification

You should output a single number – the desired radius. Output with a precision of 3 decimals. You will pass a test if the output differs from the true answer by at most 0.001.

#### Constraints

• The points are given in trigonometric (anti-clockwise) order.
• For of tests
• For of tests

#### Sample Input 1

4
0 0
1 0
1 1
0 1

#### Sample Output 1

0.293

#### Explanation for Sample Output 1

The maximum radius is obtained when the centers of the two circles are placed on one of the square's diagonals. The radius can be calculated exactly and it is

#### Sample Input 2

4
0 0
3 0
3 1
0 1

#### Sample Output 2

0.500

#### Sample Input 3

6
0 0
8 0
8 6
4 8
2 8
0 4

#### Sample Output 3

2.189