{"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\u003eIn a rainforest there are \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e treehouses high in the forest\n canopy on different trees (numbered from \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e). The \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e-th tree’s location is at\n \u003cspan class\u003d\"tex2jax_process\"\u003e$(x_ i, y_ i)$\u003c/span\u003e. The first\n \u003cspan class\u003d\"tex2jax_process\"\u003e$e$\u003c/span\u003e of them in the list\n are close enough to neighboring open land around the rainforest\n so that transportation between all of them is easy by foot.\n Some treehouses may already be connected by direct straight\n cables through the air that can allow transport between\n them.\u003c/p\u003e\n \u003cp\u003eResidents want easy transportation between all the\n treehouses and the open land, by some combination of walking\n (between those near the open land), and using one or more\n cables between treehouses. This may require the addition of\n more cables. Since the cables are expensive, they would like to\n add the smallest possible length of cable.\u003c/p\u003e\n \u003cp\u003eThe height of a cable up two trees can be set so cables can\n criss-cross other cables, and not allow any snags or crashes.\n It is not safe to try to switch between two criss-crossed\n cables in mid-air!\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe input will start with the three integers \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\le n \\le 1\\, 000$\u003c/span\u003e), \u003cspan class\u003d\"tex2jax_process\"\u003e$e$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\le e \\le n$\u003c/span\u003e), and \u003cspan class\u003d\"tex2jax_process\"\u003e$p$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$0\n \\le p \\le 1\\, 000$\u003c/span\u003e), where \u003cspan class\u003d\"tex2jax_process\"\u003e$p$\u003c/span\u003e is the number of cables in place\n already.\u003c/p\u003e\n \u003cp\u003eNext come \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e lines,\n each with two real numbers \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$y$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$|x|, |y| \\le 10\\, 000$\u003c/span\u003e) giving the\n location of a treehouse. The \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e-th coordinate pair is for the\n treehouse with ID \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e. All\n coordinate pairs are unique. Real numbers are stated as\n integers or include one digit after a decimal point.\u003c/p\u003e\n \u003cp\u003eNext come \u003cspan class\u003d\"tex2jax_process\"\u003e$p$\u003c/span\u003e lines,\n each with two integers \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e, where \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le a \u0026lt; b \\le n$\u003c/span\u003e, giving the two\n treehouse ids of an existing cable between their trees. No ID\n pair will be repeated.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eThe output is the minimum total length of new cable that\n achieves the connection goal, expressed with absolute or\n relative error less than \u003cspan class\u003d\"tex2jax_process\"\u003e$0.001$\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\u003e3 1 0\n0.0 0.0\n2.0 0.0\n1.0 2.0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4.236067\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\u003e3 1 1\n0.0 0.0\n0.5 2.0\n2.5 2.0\n1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2.000000\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\u003e3 2 0\n0.0 0.0\n2.0 0.0\n1.0 2.0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2.236067\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}