{"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 \u003cdiv style\u003d\"width:20.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/e922272fa4f21fe375916b672daa4458?v\u003d1715864761\" alt\u003d\"/problems/kiwitrees/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003e\n\n \u003cp\u003eYou are about to plant a pair of fine kiwi trees inside your\n big property. You are worried that tree branches would grow\n beyond the boundaries of your property, making your neighbours\n complain. You must also avoid planting the two trees too close\n to each other so that the branches of the trees grow into each\n other, because that could lead to a loss of fruit.\u003c/p\u003e\n\n \u003cp\u003eThe seller of the trees guaranteed that no branch or leaf\n will be farther than \u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e\u0026nbsp;meters from the trunk of its\n tree, thus we will model the trees as circles of radius\n \u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e\u0026nbsp;meters. The\n trunks are perfectly vertical.\u003c/p\u003e\n\n \u003cp\u003eLocal government regulations forbid certain shapes of\n properties. In particular, in order for government employees to\n be able to draw and handle maps of the area, each property must\n satisfy the following properties:\u003c/p\u003e\n\n \u003col class\u003d\"enumerate\"\u003e\n \u003cli\u003e\n \u003cp\u003eThe boundary is a simple polygon, i.e. the sides are\n non-intersecting and form a closed path.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eEach side length of the property is at least\n \u003cspan class\u003d\"tex2jax_process\"\u003e$30$\u003c/span\u003e meters long.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eThe angle between any two consecutive sides of the\n property must be at least \u003cspan class\u003d\"tex2jax_process\"\u003e$18$\u003c/span\u003e degrees (\u003cspan class\u003d\"tex2jax_process\"\u003e$10\\% $\u003c/span\u003e of a straight angle), and\n at most \u003cspan class\u003d\"tex2jax_process\"\u003e$144$\u003c/span\u003e degrees\n (\u003cspan class\u003d\"tex2jax_process\"\u003e$80\\% $\u003c/span\u003e of a straight\n angle, or if you will, the angle of a regular decagon).\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ol\u003e\n\n \u003cp\u003eNon-convex properties are allowed as long as the angles of\n consecutive sides follow rule 3 above, so the inner angle at a\n vertex can also be between \u003cspan class\u003d\"tex2jax_process\"\u003e$360 -\n 144 \u003d 216$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$360 - 18 \u003d\n 342$\u003c/span\u003e degrees. See Figure\u0026nbsp;1 for an example.\u003c/p\u003e\n\n \u003cdiv id\u003d\"fig:planttree sample\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/621f4ba076029cb89c57169b7cb667e5?v\u003d1715864761\" alt\u003d\"\\includegraphics[width\u003d0.50\\textwidth ]{angles}\" style\u003d\"width:50.00%\"\u003e\n \u003c/center\u003e\n\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: Illustration of Sample Input 1 and the\n solution given in Sample Output 1. All the marked angles\n are at least \u003cspan class\u003d\"tex2jax_process\"\u003e$18$\u003c/span\u003e and\n at most \u003cspan class\u003d\"tex2jax_process\"\u003e$144$\u003c/span\u003e degrees.\n \u003c/div\u003e\n \u003c/div\u003e\n\n \u003cp\u003eYour property follows these rules. Can you plant two trees\n inside the property such that their branches and leaves do not\n grow beyond its boundary, and that the branches and leaves of\n each tree do not grow into the other tree?\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe input consists of:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eOne line containing an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, where \u003cspan class\u003d\"tex2jax_process\"\u003e$3 \\le n \\le 2\\, 000$\u003c/span\u003e is the\n number of vertices of the polygon describing your\n property.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e lines\n describing one vertex each. Each such line contains two\n integers \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$y$\u003c/span\u003e, where\n \u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\le x, y \\le 10^7$\u003c/span\u003e.\n These two numbers denote the \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e- and \u003cspan class\u003d\"tex2jax_process\"\u003e$y$\u003c/span\u003e-coordinates of a vertex in\n \u003cem\u003emillimeters\u003c/em\u003e, in a clockwise order as they appear\n in the polygon.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003eAlso, each polygon side is at least \u003cspan class\u003d\"tex2jax_process\"\u003e$30$\u003c/span\u003e meters (\u003cspan class\u003d\"tex2jax_process\"\u003e$30\\, 000$\u003c/span\u003e millimeters) long and the\n angle of two segments at a vertex is at least \u003cspan class\u003d\"tex2jax_process\"\u003e$18$\u003c/span\u003e degrees and at most \u003cspan class\u003d\"tex2jax_process\"\u003e$144$\u003c/span\u003e degrees. The polygon is\n non-intersecting and closed, i.e.\u0026nbsp;the last vertex is\n connected to the first vertex.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eIf it is possible to plant two trees without their branches\n growing beyond the boundary of your property or into each\n other, output two lines, each containing two real numbers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$y$\u003c/span\u003e giving the coordinates in\n millimeters of two points where the trees can be planted.\u003c/p\u003e\n\n \u003cp\u003eOtherwise, print ā\u003ctt class\u003d\"ttfamily\"\u003eimpossible\u003c/tt\u003eā.\u003c/p\u003e\n\n \u003cp\u003eYou may assume that increasing or decreasing the radius by\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e mm will not change\n whether or not it is possible to plant the trees. Your answer\n will be accepted if the tree locations are at least\n \u003cspan class\u003d\"tex2jax_process\"\u003e$3999$\u003c/span\u003e mm away from the\n boundary and at least \u003cspan class\u003d\"tex2jax_process\"\u003e$2 \\cdot\n 3999$\u003c/span\u003e mm away from each other.\u003c/p\u003e\n\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\u003e4\n0 3000\n29000 38000\n56000 0\n28000 14000\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e32266.13633130 18219.22050526\n24266.13633130 18219.22050526\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\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\n50000 50000\n69500 73000\n99000 80000\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eimpossible\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}