{"problem":{"name":"C. Two Squares","description":{"content":"You are given two squares, one with sides parallel to the coordinate axes, and another one with sides at 45 degrees to the coordinate axes. Find whether the two squares intersect. The interior of the","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF994C"},"statements":[{"statement_type":"Markdown","content":"You are given two squares, one with sides parallel to the coordinate axes, and another one with sides at 45 degrees to the coordinate axes. Find whether the two squares intersect.\n\nThe interior of the square is considered to be part of the square, i.e. if one square is completely inside another, they intersect. If the two squares only share one common point, they are also considered to intersect.\n\n## Input\n\nThe input data consists of two lines, one for each square, both containing 4 pairs of integers. Each pair represents coordinates of one vertex of the square. Coordinates within each line are either in clockwise or counterclockwise order.\n\nThe first line contains the coordinates of the square with sides parallel to the coordinate axes, the second line contains the coordinates of the square at 45 degrees.\n\nAll the values are integer and between $-100$ and $100$.\n\n## Output\n\nPrint \"_Yes_\" if squares intersect, otherwise print \"_No_\".\n\nYou can print each letter in any case (upper or lower).\n\n[samples]\n\n## Note\n\nIn the first example the second square lies entirely within the first square, so they do intersect.\n\nIn the second sample squares do not have any points in common.\n\nHere are images corresponding to the samples:\n\n","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"iden\":\"statement\",\"content\":\"给定两个正方形，其中一个的边与坐标轴平行，另一个的边与坐标轴成 45 度角。判断这两个正方形是否相交。\\n\\n正方形的内部被视为正方形的一部分，即如果一个正方形完全位于另一个正方形内部，则它们相交。如果两个正方形仅共享一个公共点，也被认为是相交的。\\n\\n输入数据包含两行，每行对应一个正方形，每行包含 4 对整数。每对整数表示正方形的一个顶点的坐标。每行中的坐标按顺时针或逆时针顺序排列。\\n\\n第一行包含边与坐标轴平行的正方形的坐标，第二行包含边与坐标轴成 45 度角的正方形的坐标。\\n\\n所有值均为介于 $-100$ 和 $100$ 之间的整数。\\n\\n如果正方形相交，输出 \\\"_Yes_\\\"；否则输出 \\\"_No_\\\"。\\n\\n你可以以任意大小写形式输出每个字母。\\n\\n在第一个示例中，第二个正方形完全位于第一个正方形内部，因此它们相交。\\n\\n在第二个示例中，两个正方形没有任何公共点。\\n\\n以下是对应示例的图像：\\n\\n\"},{\"iden\":\"input\",\"content\":\"输入数据包含两行，每行对应一个正方形，每行包含 4 对整数。每对整数表示正方形的一个顶点的坐标。每行中的坐标按顺时针或逆时针顺序排列。第一行包含边与坐标轴平行的正方形的坐标，第二行包含边与坐标轴成 45 度角的正方形的坐标。所有值均为介于 $-100$ 和 $100$ 之间的整数。\"},{\"iden\":\"output\",\"content\":\"如果正方形相交，输出 \\\"_Yes_\\\"；否则输出 \\\"_No_\\\"。你可以以任意大小写形式输出每个字母。\"},{\"iden\":\"examples\",\"content\":\"输入0 0 6 0 6 6 0 61 3 3 5 5 3 3 1输出YES输入0 0 6 0 6 6 0 67 3 9 5 11 3 9 1输出NO输入6 0 6 6 0 6 0 07 4 4 7 7 10 10 7输出YES\"},{\"iden\":\"note\",\"content\":\"在第一个示例中，第二个正方形完全位于第一个正方形内部，因此它们相交。在第二个示例中，两个正方形没有任何公共点。以下是对应示例的图像： \"}]}","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ S_1 $ be the axis-aligned square defined by its four vertices $ (x_i, y_i) $, $ i = 1,2,3,4 $, given in cyclic order (clockwise or counterclockwise).\n\nLet $ S_2 $ be the 45°-rotated square defined by its four vertices $ (u_j, v_j) $, $ j = 1,2,3,4 $, given in cyclic order.\n\nDefine:\n\n- $ \\text{bbox}(S_1) = [x_{\\min}, x_{\\max}] \\times [y_{\\min}, y_{\\max}] $, the axis-aligned bounding box of $ S_1 $, where \n $ x_{\\min} = \\min_i x_i $, $ x_{\\max} = \\max_i x_i $, $ y_{\\min} = \\min_i y_i $, $ y_{\\max} = \\max_i y_i $.\n\n- Let $ S_2 $ be represented as a convex polygon with vertices $ (u_j, v_j) $.\n\nDetermine whether $ S_1 \\cap S_2 \\neq \\emptyset $, where:\n\n- $ S_1 = \\{ (x, y) \\in \\mathbb{R}^2 \\mid x_{\\min} \\leq x \\leq x_{\\max},\\ y_{\\min} \\leq y \\leq y_{\\max} \\} $ (closed square),\n- $ S_2 $ is the closed convex polygon formed by the given vertices.\n\n**Objective:** \nDecide if $ S_1 \\cap S_2 \\neq \\emptyset $.\n\n**Method:** \nThe squares intersect if and only if:\n\n1. The axis-aligned rectangle $ S_1 $ overlaps with the convex polygon $ S_2 $, which can be determined by:\n - Checking if any vertex of $ S_2 $ lies inside or on the boundary of $ S_1 $, OR\n - Checking if any edge of $ S_2 $ intersects any edge of $ S_1 $, OR\n - Checking if $ S_1 $ is entirely contained within $ S_2 $ (which reduces to checking if all four vertices of $ S_1 $ lie inside $ S_2 $).\n\nSince both are convex polygons, use the **Separating Axis Theorem (SAT)**:\n\n- For $ S_1 $, the potential separating axes are the unit vectors along $ \\langle 1, 0 \\rangle $ and $ \\langle 0, 1 \\rangle $.\n- For $ S_2 $, the potential separating axes are the unit vectors along the normals of its edges: since it is rotated 45°, its edge directions are $ \\langle 1,1 \\rangle $ and $ \\langle 1,-1 \\rangle $, so normals are $ \\langle 1,-1 \\rangle $ and $ \\langle 1,1 \\rangle $ (normalized).\n\nThus, the candidate separating axes are:\n- $ \\mathbf{a}_1 = \\langle 1, 0 \\rangle $\n- $ \\mathbf{a}_2 = \\langle 0, 1 \\rangle $\n- $ \\mathbf{a}_3 = \\langle 1, 1 \\rangle $ (normalized: $ \\left\\langle \\frac{1}{\\sqrt{2}}, \\frac{1}{\\sqrt{2}} \\right\\rangle $)\n- $ \\mathbf{a}_4 = \\langle 1, -1 \\rangle $ (normalized: $ \\left\\langle \\frac{1}{\\sqrt{2}}, -\\frac{1}{\\sqrt{2}} \\right\\rangle $)\n\nProject both polygons onto each axis. If there exists any axis where the projections of $ S_1 $ and $ S_2 $ do not overlap, then the squares do not intersect. Otherwise, they intersect.\n\n**Output:** \n\"**Yes**\" if $ S_1 \\cap S_2 \\neq \\emptyset $, \"**No**\" otherwise.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF994C","tags":["brute force"],"sample_group":[["0 0 6 0 6 6 0 6\n1 3 3 5 5 3 3 1","YES"],["0 0 6 0 6 6 0 6\n7 3 9 5 11 3 9 1","NO"],["6 0 6 6 0 6 0 0\n7 4 4 7 7 10 10 7","YES"]],"created_at":"2026-03-03 11:00:39"}}