- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
Yazd is the city of windcatchers. There are several famous and historical windcatchers in Yazd, including the windcatcher of Dowlatabad Garden, which is the tallest one in the world. The new mayor of Yazd is going to celebrate the history of windcatchers. To this end, he has decided to construct a new highway in the city with the following properties:
- The highway is composed of two ways of the same width.
- The two ways are adjacent, with a straight line in common (which we call the middle line).
- The highway must not pass through any windcatcher. However, windcatchers may lie on the boundary of the ways, including on the middle line.
- To celebrate the windcatchers, the highway must have at least two windcatchers exactly on its middle line.
The mayor wants to construct a highway of maximum possible width satisfying all the above conditions. However, due to a large number of windcatchers in the city, finding the best place for such a highway is not an easy task. As such, the mayor has decided to hire you to find the best location for constructing the highway. To simplify things, each windcatcher is represented by a single point in the plane. Moreover, we may assume that the constructed highway has infinite length. An example of a highway of maximum width among a set of points (windcatchers) is illustrated in the above figure.
ورودی
The first line of input contains a positive integer $n$, indicating the number of windcatchers. The next $n$ lines, each consists of a pair of integers, $x$ and $y$, indicating the location of a windcatcher in the city. Note that line $i +1$contains the location of windcatcher $i$. For simplicity, we assume that each windcatcher is a point in two dimensions, and no two windcatchers lie on the same point. Moreover, we assume that there are at least three noncollinear windcatchers in the city. It is guaranteed that $3 \leq n \leq 4,000$ and $0 \leq x,y \leq 10^9$.
خروجی
Print a float number indicating the width of a maximum-width highway satisfying all the required conditions. Your output will be considered correct if its absolute or relative error is at most $10^9$.
مثالها
ورودی نمونه ۱
3
0 0
0 1
1 0
خروجی نمونه ۱
1.000000000000
ورودی نمونه ۲
4
15 18
11 20
20 9
7 8
خروجی نمونه ۲
9.356972863938
ارسال پاسخ برای این سؤال