{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003eLast month, Sichuan province secured funding to establish\n the Great Panda National Park, a natural preserve for a\n population of more than \u003cspan class\u003d\"tex2jax_process\"\u003e$1\\,\n 800$\u003c/span\u003e giant pandas. The park will be surrounded by a\n polygonal fence. In order for researchers to track the pandas,\n wireless receivers will be placed at each vertex of the\n enclosing polygon and each animal will be outfitted with a\n wireless transmitter. Each wireless receiver will cover a\n circular area centered at the location of the receiver, and all\n receivers will have the same range. Naturally, receivers with\n smaller range are cheaper, so your goal is to determine the\n smallest possible range that suffices to cover the entire\n park.\u003c/p\u003e\n \u003cp\u003eAs an example, Figure\u0026nbsp;1 shows the park described by the\n first sample input. Notice that a wireless range of\n \u003cspan class\u003d\"tex2jax_process\"\u003e$35$\u003c/span\u003e does not suffice (a),\n while the optimal range of \u003cspan class\u003d\"tex2jax_process\"\u003e$50$\u003c/span\u003e covers the entire park (b).\u003c/p\u003e\n \u003cdiv id\u003d\"panda:sample 1\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003ctable class\u003d\"subfigure\" id\u003d\"a0000000005\" style\u003d\"display:inline-table\"\u003e\n \u003ctbody\u003e\u003ctr\u003e\n \u003ctd\u003e\u003cimg src\u003d\"CDN_BASE_URL/e95878defd3a2822336fee58c69dcdcf?v\u003d1715394164\" alt\u003d\"\\includegraphics[width\u003d10cm]{fig1a}\" style\u003d\"width:10cm\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:center\"\u003e(a) \u003cspan\u003eAn insufficient\n range for covering the park.\u003c/span\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\u003c/table\u003e\n \u003ctable class\u003d\"subfigure\" id\u003d\"a0000000006\" style\u003d\"display:inline-table\"\u003e\n \u003ctbody\u003e\u003ctr\u003e\n \u003ctd\u003e\u003cimg src\u003d\"CDN_BASE_URL/fb1b5f97d97d313ea72297a9edffc8f3?v\u003d1715394164\" alt\u003d\"\\includegraphics[width\u003d10cm]{fig1b}\" style\u003d\"width:10cm\"\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:center\"\u003e(b) \u003cspan\u003eThe minimal\n range for covering the park.\u003c/span\u003e\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\u003c/table\u003e\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: Illustration of Sample Input 1.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe first line of the input contains an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$3\n \\leq n \\leq 2\\, 000$\u003c/span\u003e) specifying the number of vertices\n of the polygon bounding the park. This is followed by\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e lines, each containing\n two integers \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$y$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$|x|, |y| \\leq 10^4$\u003c/span\u003e) that give the\n coordinates \u003cspan class\u003d\"tex2jax_process\"\u003e$(x, y)$\u003c/span\u003e of\n the vertices of the polygon in counter-clockwise order. The\n polygon is simple; that is, its vertices are distinct and no\n two edges of the polygon intersect or touch, except that\n consecutive edges touch at their common vertex.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eDisplay the minimum wireless range that suffices to cover\n the park, with an absolute or relative error of at most\n \u003cspan class\u003d\"tex2jax_process\"\u003e$10^{-6}$\u003c/span\u003e.\u003c/p\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n0 0\n170 0\n140 30\n60 30\n0 70\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e50\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n0 0\n170 0\n140 30\n60 30\n0 100\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e51.538820320\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 3\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n0 0\n1 2\n1 5\n0 2\n0 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1.581138830\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}