P1783 Beach Defense

Student WLP has recently become obsessed with an online multiplayer battle game (now he finally knows why JOHNKRAM’s daily Luogu grinding efficiency is so low), but he is troubled by the game, because his shipyard and warehouse by the sea are always raided by enemies. So WLP used his full and substantial brain (perhaps more of the former) and came up with a good idea: he divided the beach into several columns perpendicular to the coastline, and placed several signal towers on some of these columns, trying to monitor the entire beach. However, WLP is very impatient. After building the signal towers, he realized he still needed to power them for them to work (well, duh). Each tower has a working radius, and all enemies within a circular area cannot escape its surveillance. However, WLP found that the enemies are very cunning: unless he completely seals off the route, his enemies can take an arbitrarily curved path (not necessarily through integer points, but they will not leave the boundary formed by column $0$ and column $N$) to steal his stuff. So WLP started thinking: what working radius should he give to each signal tower in order to completely block all paths from the beach to the inland? He once again used his full and substantial brain, thought for a math class, and still didn’t figure it out. Therefore, he asked the “shen-niao” LZZ for help (uh... did this expose CSUNSHINE’s identity?). Finally, after WLP’s pleading: “ %^!\*@#!\*(\*^!\*#@\$^& (countless cute scenes omitted here)”, the mighty LZZ wrote a program and solved the problem within one second. But the evil LZZ decided to share this tough problem with countless innocent OIers, so now it’s your turn.

The first line contains two integers $N$ and $M$, representing the columns $0,1,2,\cdots,N$ into which WLP divided the beach, and the number of signal towers. Lines $2$ to $M+1$: each line contains two numbers $X_i$, $Y_i$, indicating the column index and the distance from the beach of the $i$-th ($1,2,3,\cdots,M$) signal tower.

Output one real number: the minimal working radius, rounded to two decimal places.

- Constraints and Conventions - For $10\%$ of the testdata: $1 \le M \le 10$, $1 \le Y_i \le 100$. - For $30\%$ of the testdata: $1 \le M \le 50$, $1 \le Y_i \le 1,000$. - For $80\%$ of the testdata: $1 \le M \le 500$, $1 \le Y_i \le 1,000$. - For $100\%$ of the testdata: $1 \le M \le 800$, $1 \le N \le 1000$, $1 \le X_i \le N$, $1 \le Y_i \le 100,000$. - Note “Blocking the beach” means that the enemy’s penetration depth is bounded. If the enemy can bypass all the signal towers and then advance indefinitely inland, the route is not completely blocked. Translated by ChatGPT 5