Design a Garden Border

Time Limit: 3000 Ms

Memory Limit: 65535 Kb

Description

One day you realize your dream and become a fabulous designer. A project manager comes to find you to do some businesses. Due to your wonderful experiences and designing skills, he decides to make a gigantic investment to design a garden border. Now it is your turn to make that happen. For the sake of his contentment, you must follow all his requirements that he mentions:

1. The garden is a convexpolygon. The garden is inside the border and is line-parallel to the border. Between the border and the garden stands the corridor around. The width of the corridor is D (D>=0).

2. The area of the convexpolygon consisting of all the borders must be at least S. (remember the convexpolygon’s area contains the garden’s area inside)

3. On the borders, the manager wants to place a water spray, which has an R spray range. He announces that in your design you must make sure that every point on the borders where the water spray sets can cover all the garden area to make the garden watered.

4. He will give you the garden point by point in random order, totally N points.

(we assure that no three points in one line and these points are all vertexes) He will also show you the base requirement: S, R. And you must give the range of D.

This is a picture to help you to better understand the design. If legal D does not exist, puts a single line: no appropriate design

Input

Multiple cases, end with EOF;

In each case, an integer N, 3<=N<=10000;

Following N lines: (Xi, Yi)     |Xi|<109 |Yi|<109

Two floating-point numbers: S(109 >S>=0),R(109 >R>=0);


Output

D’s range:

Two floating-point numbers, split by blank, just rounded the answers to three digits(the error of answers in range of 0.001 will be accepted), smaller one comes first.

Sample Input

4
(0,0)
(1,1)
(1,0)
(0,1)
1.000 2.829
4
(1,0)
(1,1)
(0,1)
(0,0)
1 1

Sample Output

0.000 1.000
no appropriate design

Hint

None

Source

2013 ACM-ICPC China Nanjing Invitational Prog

提交代码