{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"The 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."},{"iden":"output","content":"For each test case, print on a single line, a single number representing the area of intersection, rounded to four decimal places."},{"iden":"examples","content":"Input25 30 3 1 1 3 1 3 5 1 51 3 5 3 3 63 3-1 -1 -2 -1 -1 -21 1 2 1 1 2Output2.66670.0000"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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 $.","simple_statement":"You are given a grid of size M×N (all cells start at 0).  \nQ players take turns: each chooses a rectangle and adds a value A to all cells inside it.  \nFind the maximum value in the grid after all moves.  \n\nNote: M can be up to 10^9, but N is at most 4000.","has_page_source":false}