{"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:30.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/a242a01e1915cac9589d04117730c25f?v\u003d1715181880\" alt\u003d\"/problems/unusualdarts/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003e\n\n \u003cp\u003eIn the game of Unusual Darts, Alice throws seven darts onto\n a \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e-foot by \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e-foot board, and then Bob may or\n may not throw three darts.\u003c/p\u003e\n\n \u003cp\u003eAlice’s seven darts define a polygon by the order in which\n they are thrown, with the perimeter of the polygon connecting\n Dart\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to\n Dart\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e to\n Dart\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e to\n Dart\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e to\n Dart\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$5$\u003c/span\u003e to\n Dart\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$6$\u003c/span\u003e to\n Dart\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$7$\u003c/span\u003e, and back to\n Dart\u0026nbsp;\u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e. If the\n polygon so defined is not simple (meaning it intersects itself)\n then Alice loses. If the polygon is simple, then Bob throws\n three darts. He is not a very good player, so although his\n darts always land on the board, they land randomly on the dart\n board following a uniform distribution. If all three of these\n darts land within the interior of the polygon, Bob wins,\n otherwise Alice wins.\u003c/p\u003e\n\n \u003cp\u003eFor this problem you are given the locations of Alice’s\n darts (which form a simple polygon) and the probability that\n Bob wins. Your job is to determine the order in which Alice\n threw her darts.\u003c/p\u003e\n\n \u003cdiv class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/4877052073a7b10d8fed0c4052b0be3c?v\u003d1715181880\" alt\u003d\"\\includegraphics[width\u003d0.8\\textwidth ]{UnusualDarts.png}\" style\u003d\"width:80.00%\"\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe first line of input contains an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\\leq N\\leq 1\\, 000$\u003c/span\u003e), indicating the\n number of Darts games that follow. Each game description has\n \u003cspan class\u003d\"tex2jax_process\"\u003e$8$\u003c/span\u003e lines. Lines\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e through \u003cspan class\u003d\"tex2jax_process\"\u003e$7$\u003c/span\u003e each have a pair of real numbers\n with \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e digits after the\n decimal point. These indicate the \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$y$\u003c/span\u003e coordinates of Alice’s seven darts\n (\u003cspan class\u003d\"tex2jax_process\"\u003e$x_1~ y_1$\u003c/span\u003e to\n \u003cspan class\u003d\"tex2jax_process\"\u003e$x_7~ y_7$\u003c/span\u003e), which are all\n at distinct locations. All coordinates are given in feet, in\n the range (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\le x_ i, y_ i \\le\n 2$\u003c/span\u003e). The \u003cspan class\u003d\"tex2jax_process\"\u003e$8^\\textrm\n {th}$\u003c/span\u003e line contains a real number \u003cspan class\u003d\"tex2jax_process\"\u003e$p$\u003c/span\u003e with \u003cspan class\u003d\"tex2jax_process\"\u003e$5$\u003c/span\u003e digits after the decimal point,\n giving the probability that Bob wins. In all test cases,\n Alice’s darts do form a simple polygon, but not necessarily in\n the order given.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eFor each Darts game, output the order in which the darts\n could have been thrown, relative to the order they were given\n in the input, so that Bob wins with probability \u003cspan class\u003d\"tex2jax_process\"\u003e$p$\u003c/span\u003e. If several answers are possible,\n give the one that is lexicographically least. Any ordering that\n would give Bob a probability of winning within \u003cspan class\u003d\"tex2jax_process\"\u003e$10^{-5}$\u003c/span\u003e of the given value of\n \u003cspan class\u003d\"tex2jax_process\"\u003e$p$\u003c/span\u003e is considered a valid\n ordering.\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\u003e3\n0.000 0.000\n0.000 2.000\n1.000 1.800\n1.000 0.200\n1.800 1.000\n2.000 0.000\n2.000 2.000\n0.61413\n0.000 0.000\n0.000 2.000\n1.000 1.800\n1.000 0.200\n1.800 1.000\n2.000 0.000\n2.000 2.000\n0.12500\n0.000 0.000\n0.000 1.900\n0.400 2.000\n1.700 0.000\n1.800 2.000\n2.000 0.200\n2.000 0.600\n0.86416\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 2 3 7 5 6 4\n1 4 3 2 7 5 6\n1 2 3 5 7 6 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}