{"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\u003eThe Intrusion and Crime Prevention Company (ICPC) builds\n intrusion detection systems for homes and businesses. The\n International Collegiate Programming Contest (in a strange\n coincidence also known as ICPC) is considering hiring the\n company to secure the room that contains the problem set for\n next year’s World Finals.\u003c/p\u003e\n \u003cp\u003eThe contest staff wants to prevent the intrusion attempts\n that were made in past years, such as rappelling down the\n outside of the building to enter through a window, crawling\n through air ducts, impersonating Bill Poucher, and the creative\n use of an attack submarine. For that reason, the problems will\n be stored in a room that has a single door and no other\n exits.\u003c/p\u003e\n \u003cp\u003eICPC (the company) proposes to install sensors on the four\n sides of the door, where pairs of sensors are connected by\n wires. If somebody opens the door, any connected sensor pair\n will detect this and cause an alarm to sound.\u003c/p\u003e\n \u003cp\u003eThe system has one design flaw, however. An intruder might\n cut the wires before opening the door. To assess the security\n of the system, you need to determine the minimum number of line\n segments that cut all wires. Figure\u0026nbsp;1 shows two\n configurations of wires on the door (corresponding to the two\n sample inputs), and minimum-size cuts that intersect all\n wires.\u003c/p\u003e\n \u003cdiv id\u003d\"fig:cut1\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003ctable cellspacing\u003d\"0\" class\u003d\"tabular\"\u003e\n \u003ctbody\u003e\u003ctr\u003e\n \u003ctd style\u003d\"text-align:center\"\u003e\n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/5e363440bd72bd2deab4fde8a3ecedef?v\u003d1715477524\" alt\u003d\"\\includegraphics[width\u003d6cm]{sample1}\" style\u003d\"width:6cm\"\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:center\"\u003e\n \u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/0485dc382d130829bfa7f1a8d0143446?v\u003d1715477524\" alt\u003d\"\\includegraphics[width\u003d6cm]{sample2}\" style\u003d\"width:6cm\"\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:center\"\u003e\n \u003cp\u003e(a) Four wires (blue) that can be intersected with\n a single cut (red).\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:center\"\u003e\n \u003cp\u003e(b) Five wires that need two cuts.\u003c/p\u003e\n \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: Illustrations of Sample Inputs 1 and 2.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe input starts with a line containing three integers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$w$\u003c/span\u003e, and \u003cspan class\u003d\"tex2jax_process\"\u003e$h$\u003c/span\u003e, which represent the number of\n wires installed (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq n \\leq\n 10^6$\u003c/span\u003e) and the dimensions of the door (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq w, h \\leq 10^8$\u003c/span\u003e). This is\n followed by \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e lines,\n each describing a wire placement. Each of these lines contains\n four integers \u003cspan class\u003d\"tex2jax_process\"\u003e$x_1$\u003c/span\u003e,\n \u003cspan class\u003d\"tex2jax_process\"\u003e$y_1$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$x_2$\u003c/span\u003e, and \u003cspan class\u003d\"tex2jax_process\"\u003e$y_2$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\leq x_1, x_2 \\leq w$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\leq y_1, y_2 \\leq h$\u003c/span\u003e), meaning\n that a wire goes from \u003cspan class\u003d\"tex2jax_process\"\u003e$(x_1,\n y_1)$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$(x_2,\n y_2)$\u003c/span\u003e. Each wire connects different sides of the door.\n No wire is anchored to any of the four corners of the door. All\n locations in the input are distinct.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eDisplay a minimum-size set of straight line cuts that\n intersect all wires. First, display the number of cuts needed.\n Then display the cuts, one per line in the format \u003cspan class\u003d\"tex2jax_process\"\u003e$x_1$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$y_1$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$x_2$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$y_2$\u003c/span\u003e for the cut between \u003cspan class\u003d\"tex2jax_process\"\u003e$(x_1,y_1)$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$(x_2,y_2)$\u003c/span\u003e. Each cut has to start and\n end on different sides of the door. Cuts cannot start or end\n closer than \u003cspan class\u003d\"tex2jax_process\"\u003e$10^{-6}$\u003c/span\u003e to\n any wire anchor location or any corner of the door.\u003c/p\u003e\n \u003cp\u003eCuts may be displayed in any order. The start and end\n locations of each cut may be displayed in either order. If\n there are multiple sets of cuts with the same minimum size,\n display any of them.\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\u003e4 4 6\n0 1 4 4\n0 5 2 0\n0 3 3 6\n2 6 4 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n0 4 4 3\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 4 6\n0 2 2 0\n0 3 2 6\n1 6 3 0\n1 0 4 4\n3 6 4 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n0 4 4 4.5\n0 1 4 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}