{"problem":{"name":"J. Polygons Intersection","description":{"content":"We will not waste your time, it is a straightforward problem. Given multiple polygons, calculate the area of their intersection. For simplicity, there will be exactly 2 polygons both of them are conve","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":65536},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10095J"},"statements":[{"statement_type":"Markdown","content":"We will not waste your time, it is a straightforward problem. Given multiple polygons, calculate the area of their intersection. For simplicity, there will be exactly 2 polygons both of them are convex, given in the counterclockwise order and have non-zero areas. Furthermore, in one polygon a vertex won't be on the sides of the other one. The figure below demonstrates the first test case.\n\nThe first line of the input will be a single integer T, the number of test cases (1  ≤  T  ≤  20). each test case contains two integers (3  ≤  N, M  ≤  40) Then a line contains N pairs of integers xi, yi (-1000  ≤  xi, yi  ≤  1000) coordinates of the ith vertex of polygon A, followed by a line contains M pairs of integers xj, yj (-1000  ≤  xj, yj  ≤  1000) coordinates of the jth vertex of polygon B. The coordinates are separated by a single space.\n\nFor each test case, print on a single line, a single number representing the area of intersection, rounded to four decimal places.\n\n## Input\n\nThe first line of the input will be a single integer T, the number of test cases (1  ≤  T  ≤  20). each test case contains two integers (3  ≤  N, M  ≤  40) Then a line contains N pairs of integers xi, yi (-1000  ≤  xi, yi  ≤  1000) coordinates of the ith vertex of polygon A, followed by a line contains M pairs of integers xj, yj (-1000  ≤  xj, yj  ≤  1000) coordinates of the jth vertex of polygon B. The coordinates are separated by a single space.\n\n## Output\n\nFor each test case, print on a single line, a single number representing the area of intersection, rounded to four decimal places.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ Q \\in \\mathbb{Z} $ be the number of players.  \nLet $ M, N \\in \\mathbb{Z} $ be the dimensions of the grid, with $ 1 \\leq i \\leq M $, $ 1 \\leq j \\leq N $.  \nLet $ A_k \\in \\mathbb{Z} $, $ (Y_{1,k}, X_{1,k}), (Y_{2,k}, X_{2,k}) \\in \\mathbb{Z}^2 $ for $ k \\in \\{1, \\dots, Q\\} $ define the $ k $-th operation: add $ A_k $ to all cells in the rectangle $ [Y_{1,k}, Y_{2,k}] \\times [X_{1,k}, X_{2,k}] $.  \n\n**Constraints**  \n1. $ 1 \\leq Q \\leq 10^4 $  \n2. $ 5 \\leq M \\leq 10^9 $, $ 5 \\leq N \\leq 4000 $  \n3. $ 1 \\leq X_{1,k} \\leq X_{2,k} \\leq N $, $ 1 \\leq Y_{1,k} \\leq Y_{2,k} \\leq M $  \n4. $ -100 \\leq A_k \\leq 100 $  \n\n**Objective**  \nCompute $ \\max_{1 \\leq i \\leq M,\\, 1 \\leq j \\leq N} \\left( \\sum_{k=1}^{Q} A_k \\cdot \\mathbf{1}_{[Y_{1,k}, Y_{2,k}]}(i) \\cdot \\mathbf{1}_{[X_{1,k}, X_{2,k}]}(j) \\right) $,  \nwhere $ \\mathbf{1}_{[a,b]}(x) = 1 $ if $ a \\leq x \\leq b $, else $ 0 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10095J","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}