{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\n你的老板曾经得到了一张宝藏地图的许多副本。不幸的是,所有的副本现在都被打碎成了许多矩形的碎片,更糟糕的是,他还丢失了一些碎片。幸运的是,可以确定每个碎片在原始地图中的位置。现在老板要求你,这位有才华的程序员,用这些碎片制作一张完整的宝藏地图。你只需要制作一张完整的地图,不需要使用所有的碎片。但是记住,碎片之间不允许重叠(参见示例2)。\n\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003e输入\u003c/b\u003e\u003c/p\u003e\n\n\u003cp\u003e\n输入的第一行包含一个整数 \u003ci\u003eT\u003c/i\u003e (\u003ci\u003eT\u003c/i\u003e \u0026lt;\u003d 500),表示案例的数量。\n\u003c/p\u003e\n\n\u003cp\u003e\n对于每个案例,第一行包含三个整数 \u003ci\u003en\u003c/i\u003e \u003ci\u003em\u003c/i\u003e \u003ci\u003ep\u003c/i\u003e (1 \u0026lt;\u003d \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e \u0026lt;\u003d 30, 1 \u0026lt;\u003d \u003ci\u003ep\u003c/i\u003e \u0026lt;\u003d 500),表示地图的宽度和高度,以及碎片的数量。然后是 \u003ci\u003ep\u003c/i\u003e 行,每行包含四个整数 \u003ci\u003ex1\u003c/i\u003e \u003ci\u003ey1\u003c/i\u003e \u003ci\u003ex2\u003c/i\u003e \u003ci\u003ey2\u003c/i\u003e (0 \u0026lt;\u003d \u003ci\u003ex1\u003c/i\u003e \u0026lt; \u003ci\u003ex2\u003c/i\u003e \u0026lt;\u003d \u003ci\u003en\u003c/i\u003e, 0 \u0026lt;\u003d \u003ci\u003ey1\u003c/i\u003e \u0026lt; \u003ci\u003ey2\u003c/i\u003e \u0026lt;\u003d \u003ci\u003em\u003c/i\u003e),其中 (x1, y1) 是矩形碎片左下角的坐标,(x2, y2) 是原始地图右上角的坐标。\n\u003c/p\u003e\n\n\u003cp\u003e\n案例之间用一个空行分隔。\n\n\u003c/p\u003e\u003ccenter\u003e\n\u003cimg src\u003d\"CDN_BASE_URL/1ee386fdb85ea433f3f7a6fe05cf2f67?v\u003d1712185013\"\u003e\n\u003c/center\u003e\n\u003cp\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003e输出\u003c/b\u003e\u003c/p\u003e\n\n如果你能用这些碎片制作一张完整的地图,输出你需要的最少碎片数量。\n\n如果无法制作一张完整的地图,只需输出 -1。\n\n\u003cp\u003e\u003cb\u003e示例输入\u003c/b\u003e\u003c/p\u003e\n\n\u003cpre\u003e3\n5 5 1\n0 0 5 5\n\n5 5 2\n0 0 3 5\n2 0 5 5\n\n30 30 5\n0 0 30 10\n0 10 30 20\n0 20 30 30\n0 0 15 30\n15 0 30 30\n\u003c/pre\u003e\n\n\u003cp\u003e\u003cb\u003e示例输出\u003c/b\u003e\u003c/p\u003e\n\n\u003cpre\u003e1\n-1\n2\n\u003c/pre\u003e\n\n\u003cp\u003e\u003cb\u003e提示\u003c/b\u003e\u003c/p\u003e\n\n\u003cp\u003e\n对于示例1,只有一个碎片就是一张完整的地图。\n\u003c/p\u003e\n\n\u003cp\u003e\n对于示例2,两个碎片可能会重叠,所以无法制作一张完整的宝藏地图。\n\u003c/p\u003e\n\n\u003cp\u003e\n对于示例3,你可以通过使用前3个碎片或后2个碎片来制作一张地图,后一种方法需要更少的碎片。\n\u003c/p\u003e"}}]}