303601: CF696F. ...Dary!

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

...Dary!

题意翻译

给定一个$n$个点的凸多边形,按逆时针顺序给出每个顶点的坐标$(x_i,y_i)$,保证任意三点不共线。 要求最小化实数$r$,使得可以在多边形内部(可以在边界或顶点上)选出两个可以重合的点,令多边形每条边所在的直线上存在至少一点(可以不在边上)距离两个点之一不超过$r$,即以这两点作半径为$r$的圆,与多边形每条边所在直线至少有一个交点。 输出最小的$r$和选择的点的坐标,当绝对或相对误差不超过$10^{-6}$时答案被认为是正确的。

题目描述

Barney has finally found the one, a beautiful young lady named Lyanna. The problem is, Lyanna and Barney are trapped in Lord Loss' castle. This castle has shape of a convex polygon of $ n $ points. Like most of castles in Demonata worlds, this castle has no ceiling. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF696F/c4b0dd1b2d0733e52dd3ceb8bf450d52a92808ed.png)Barney and Lyanna have an escape plan, but it requires some geometry knowledge, so they asked for your help. Barney knows that demons are organized and move in lines. He and Lyanna want to wait for the appropriate time so they need to watch for the demons. Each of them wants to stay in a point inside the castle (possibly on edges or corners), also they may stay in the same position. They both want to pick a real number $ r $ and watch all points in the circles with radius $ r $ around each of them (these two circles may overlap). ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF696F/ad91b6cb64c298e776196c7de333e077a1acafad.png)We say that Barney and Lyanna are watching carefully if and only if for every edge of the polygon, at least one of them can see at least one point on the line this edge lies on, thus such point may not be on the edge but it should be on edge's line. Formally, each edge line should have at least one common point with at least one of two circles. The greater $ r $ is, the more energy and focus they need. So they asked you to tell them the minimum value of $ r $ such that they can watch carefully.

输入输出格式

输入格式


The first line of input contains a single integer $ n $ ( $ 3<=n<=300 $ ) — the number of castle polygon vertices. The next $ n $ lines describe the polygon vertices in counter-clockwise order. $ i $ -th of them contains two integers $ x_{i} $ and $ y_{i} $ ( $ |x_{i}|,|y_{i}|<=10^{4} $ ) — the coordinates of $ i $ -th point of the castle. It is guaranteed that given points form a convex polygon, in particular, any three of them do not line on the same line.

输出格式


In the first line print the single number $ r $ — minimum radius of guys' watching circles. In the second line print the pair of coordinates of point where Barney should stay. In the third line print the pair of coordinates of point where Lyanna should stay. Points should lie inside the polygon. Coordinates may not be integers. If there are multiple answers print any of them. Your answer will be considered correct if its absolute or relative error doesn't exceed $ 10^{-6} $ .

输入输出样例

输入样例 #1

4
-41 67
-16 20
25 25
-36 85

输出样例 #1

0
-16 20
-36 85

输入样例 #2

7
-7 54
-5 31
-2 17
20 19
32 23
34 27
26 57

输出样例 #2

2.9342248
32.019503 23.0390067
-6.929116 54.006444

说明

In the first example guys can stay in opposite corners of the castle.

Input

题意翻译

给定一个$n$个点的凸多边形,按逆时针顺序给出每个顶点的坐标$(x_i,y_i)$,保证任意三点不共线。 要求最小化实数$r$,使得可以在多边形内部(可以在边界或顶点上)选出两个可以重合的点,令多边形每条边所在的直线上存在至少一点(可以不在边上)距离两个点之一不超过$r$,即以这两点作半径为$r$的圆,与多边形每条边所在直线至少有一个交点。 输出最小的$r$和选择的点的坐标,当绝对或相对误差不超过$10^{-6}$时答案被认为是正确的。

加入题单

上一题 下一题 算法标签: