{"problem":{"name":"A. Hasan the lazy judge","description":{"content":"Since Hasan was too lazy to write a story for this problem, so we'll say it clear: Given $N$ Horizontal lines and $M$ Vertical lines, you need to find the Longest plus sign formed by the intersection","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10216A"},"statements":[{"statement_type":"Markdown","content":"Since Hasan was too lazy to write a story for this problem, so we'll say it clear:\n\nGiven $N$ Horizontal lines and $M$ Vertical lines, you need to find the Longest plus sign formed by the intersection of exactly one vertical line with one horizontal line.\n\nThe length of the plus sign is defined by the length of its shortest side (the minimum length of the segments $[ C, L 1 ]$, $[ C, L 2 ]$, $[ C, L 3 ]$, $[ C, L 4 ]$.\n\nFirst line of input will be $T$ number of test cases.\n\nEach test case will start with two numbers, $N$ and $M$ the number of Horizontal lines and the number of vertical lines.\n\nNext $N$ lines contain three space separated numbers, $X_1$, $X_2$ and $Y$, the starting and ending $X$ coordinates of the horizontal line, and It's $Y$ coordinate.\n\nNext $M$ lines contain three space separated numbers, $Y_1$, $Y_2$ and $X$, the starting and ending $Y$ coordinates of the horizontal line, and It's $X$ coordinate.\n\n$1 <= N, M <= 10^5$\n\n$1 <= c o o r d i n a t e s <= 10^5$ and all the coordinates are integers.\n\nFor each test case print one line, containing the length of the longest plus sign.\n\n## Input\n\nFirst line of input will be $T$ number of test cases.Each test case will start with two numbers, $N$ and $M$ the number of Horizontal lines and the number of vertical lines.Next $N$ lines contain three space separated numbers, $X_1$, $X_2$ and $Y$, the starting and ending $X$ coordinates of the horizontal line, and It's $Y$ coordinate.Next $M$ lines contain three space separated numbers, $Y_1$, $Y_2$ and $X$, the starting and ending $Y$ coordinates of the horizontal line, and It's $X$ coordinate.$1 <= N, M <= 10^5$$1 <= c o o r d i n a t e s <= 10^5$ and all the coordinates are integers.\n\n## Output\n\nFor each test case print one line, containing the length of the longest plus sign.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ \\mathcal{H} = \\{ (x_{1,i}, x_{2,i}, y_i) \\mid i \\in \\{1, \\dots, N\\} \\} $ be the set of horizontal line segments, where $ x_{1,i} \\le x_{2,i} $ and $ y_i $ is the constant $ y $-coordinate.  \n- Let $ \\mathcal{V} = \\{ (y_{1,j}, y_{2,j}, x_j) \\mid j \\in \\{1, \\dots, M\\} \\} $ be the set of vertical line segments, where $ y_{1,j} \\le y_{2,j} $ and $ x_j $ is the constant $ x $-coordinate.  \n\n**Constraints**  \n1. $ 1 \\le T \\le \\text{unknown} $ (not bounded in input)  \n2. $ 1 \\le N, M \\le 10^5 $  \n3. All coordinates are integers in $ [1, 10^5] $  \n\n**Objective**  \nFor each test case, find the maximum value of:  \n$$\n\\min\\left( \\min(x_j - x_{1,i}, x_{2,i} - x_j), \\min(y_i - y_{1,j}, y_{2,j} - y_i) \\right)\n$$  \nover all pairs $ ((x_{1,i}, x_{2,i}, y_i), (y_{1,j}, y_{2,j}, x_j)) \\in \\mathcal{H} \\times \\mathcal{V} $ such that:  \n- $ x_{1,i} \\le x_j \\le x_{2,i} $ (vertical line intersects horizontal line in $ x $),  \n- $ y_{1,j} \\le y_i \\le y_{2,j} $ (horizontal line intersects vertical line in $ y $).  \n\nOutput the maximum such value across all valid intersections.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10216A","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}