25226번 - Cookie Cutter 스페셜 저지다국어

Everyone loves chocolate chip cookies! Which unfortunately means sharing sometimes. In this case, you have generously agreed to split a square chocolate chip cookie with your friend.

Because it is your cookie, you get to choose how to cut the cookie, and which piece to give to your friend. You can split the cookie along any straight line that passes through the cookie; the line need not be axis-aligned.

You know the location of all chocolate chips in the cookie. Because you prefer a cookie that is dense with chocolate chips, you want to optimize your cut to produce the best possible split. You accomplish this by maximizing the difference between the fraction of chocolate chips in your piece and the fraction of cookie area in your piece.

The first line of input contains two space-separated integers $n$ ($2 \leq n \leq 10\,000$) and $m$ ($1 \leq m \leq 3\,000$), where $n$ is the side length of the square cookie, and $m$ is the number of chocolate chips in the cookie.

The next $m$ lines each contain two space-separated integers $x$ and $y$ ($0 < x, y < n$) defining the location of a chocolate chip in the cookie. All chocolate chip locations are distinct. If a chocolate chip lies exactly on the cut, you can decide which piece of the cookie it goes to.

Output a real number, which is the maximum possible value for $\frac{b}{m} - \frac{a}{n^2}$, where $a$ is the area of cookie that you get, and $b$ is the number of chocolate chips in your piece of the cookie. The answer is accepted with absolute or relative error at most $10^{-6}$.

Illustration of Sample Case 1.