{"raw_statement":[{"iden":"statement","content":"Bearland is a big square on the plane. It contains all points with coordinates not exceeding 106 by the absolute value.\n\nThere are _n_ houses in Bearland. The _i_\\-th of them is located at the point (_x__i_, _y__i_). The _n_ points are distinct, but some subsets of them may be collinear.\n\nBear Limak lives in the first house. He wants to destroy his house and build a new one somewhere in Bearland.\n\nBears don't like big changes. For every three points (houses) _p__i_, _p__j_ and _p__k_, the sign of their cross product (_p__j_ - _p__i_) × (_p__k_ - _p__i_) should be the same before and after the relocation. If it was negative/positive/zero, it should still be negative/positive/zero respectively. This condition should be satisfied for all triples of indices (_i_, _j_, _k_), possibly equal to each other or different than 1. Additionally, Limak isn't allowed to build the house at the point where some other house already exists (but it can be the point where his old house was).\n\nIn the formula above, we define the difference and the cross product of points (_a__x_, _a__y_) and (_b__x_, _b__y_) as:\n\n<center>(_a__x_, _a__y_) - (_b__x_, _b__y_) = (_a__x_ - _b__x_, _a__y_ - _b__y_), </center><center>(_a__x_, _a__y_) × (_b__x_, _b__y_) = _a__x_·_b__y_ - _a__y_·_b__x_.</center>Consider a set of possible new placements of Limak's house. Your task is to find the area of that set of points.\n\nFormally, let's say that Limak chooses the new placement randomly (each coordinate is chosen independently uniformly at random from the interval \\[ - 106, 106\\]). Let _p_ denote the probability of getting the allowed placement of new house. Let _S_ denote the area of Bearland (_S_ = 4·1012). Your task is to find _p_·_S_."},{"iden":"input","content":"The first line of the input contains an integer _T_ (1 ≤ _T_ ≤ 500) — the number of test cases. The description of the test cases follows.\n\nThe first line of the description of a test case contains an integer _n_ (3 ≤ _n_ ≤ 200 000) — the number of houses.\n\nThe _i_\\-th of the next _n_ lines contains two integers _x__i_ and _y__i_ ( - 106 ≤ _x__i_, _y__i_ ≤ 106) — coordinates of the _i_\\-th house. No two houses are located at the same point in the same test case. Limak lives in the first house.\n\nThe sum of _n_ won't exceed 200 000."},{"iden":"output","content":"Print one real value, denoting the area of the set of points that are possible new placements of Limak's house.\n\nYour answer will be considered correct if its absolute or relative error doesn't exceed 10 - 6. More precisely, let the jury's answer be _b_, and your answer be _a_. Then your answer will be accepted if and only if ."},{"iden":"example","content":"Input\n\n4\n4\n5 3\n0 1\n10 1\n3 51\n3\n-999123 700000\n-950000 123456\n-950000 987654\n3\n2 3\n10 -1\n-4 6\n5\n1 3\n5 2\n6 1\n4 4\n-3 3\n\nOutput\n\n250.000000000000\n100000000000.000000000000\n0.000000000000\n6.562500000000"},{"iden":"note","content":"In the sample test, there are 4 test cases.\n\nIn the first test case, there are four houses and Limak's one is in (5, 3). The set of valid new placements form a triangle with vertices in points (0, 1), (10, 1) and (3, 51), without its sides. The area of such a triangle is 250.\n\nIn the second test case, the set of valid new placements form a rectangle of width 50 000 and height 2 000 000. Don't forget that the new placement must be inside the big square that represents Bearland.\n\nIn the third test case, the three given points are collinear. Each cross product is equal to 0 and it should be 0 after the relocation as well. Hence, Limak's new house must lie on the line that goes through the given points. Since it must also be inside the big square, new possible placements are limited to some segment (excluding the two points where the other houses are). The area of any segment is 0."}],"translated_statement":[{"iden":"statement","content":"Bearland 是平面上的一个大正方形，包含所有坐标绝对值不超过 $10^6$ 的点。\n\nBearland 中有 $n$ 座房屋，第 $i$ 座位于点 $(x_i, y_i)$。这 $n$ 个点互不相同，但其中某些子集可能共线。\n\n熊 Limak 住在第一座房屋中。他想拆除自己的房屋，并在 Bearland 的某个位置重建一座新屋。\n\n熊不喜欢大的变化。对于任意三个点（房屋）$p_i$、$p_j$ 和 $p_k$，它们的叉积 $(p_j - p_i) × (p_k - p_i)$ 的符号在搬迁前后必须保持一致。如果原来是负数/正数/零，则搬迁后仍必须为负数/正数/零。此条件必须对所有三元组索引 $(i, j, k)$ 成立，这些索引可能彼此相等，也可能不同于 $1$。此外，Limak 不允许在已有其他房屋的点上建房（但可以在他旧屋的位置建房）。\n\n在上述公式中，我们定义点 $(a_x, a_y)$ 和 $(b_x, b_y)$ 的差与叉积为：\n\n考虑 Limak 新屋所有可能的放置位置集合。你的任务是求出该点集的面积。\n\n形式化地说，假设 Limak 随机选择新位置（每个坐标独立且均匀地从区间 $[-10^6, 10^6]$ 中选取）。令 $p$ 表示获得合法新位置的概率。令 $S$ 表示 Bearland 的面积（$S = 4 × 10^{12}$）。你的任务是求出 $p × S$。\n\n输入的第一行包含一个整数 $T$（$1 ≤ T ≤ 500$）——测试用例的数量。接下来是各测试用例的描述。\n\n每个测试用例的第一行包含一个整数 $n$（$3 ≤ n ≤ 200 000$）——房屋的数量。\n\n接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$-10^6 ≤ x_i, y_i ≤ 10^6$）——第 $i$ 座房屋的坐标。同一测试用例中，没有两座房屋位于同一点。Limak 住在第一座房屋中。\n\n所有测试用例的 $n$ 之和不超过 $200 000$。\n\n请输出一个实数，表示 Limak 新屋所有可能放置位置的点集面积。\n\n你的答案若绝对误差或相对误差不超过 $10^{-6}$，则被视为正确。更精确地说，设评判程序的答案为 $b$，你的答案为 $a$，则当且仅当 $\\frac{|a - b|}{\\max(1, |b|)} \\leq 10^{-6}$ 时，你的答案会被接受。\n\n在样例测试中，共有 $4$ 个测试用例。\n\n在第一个测试用例中，有四座房屋，Limak 的房屋位于 $(5, 3)$。合法的新位置构成一个三角形，其顶点为 $(0, 1)$、$(10, 1)$ 和 $(3, 51)$，但不包含边界。该三角形的面积为 $250$。\n\n在第二个测试用例中，合法的新位置构成一个宽为 $50 000$、高为 $2 000 000$ 的矩形。别忘了新位置必须位于代表 Bearland 的大正方形内部。\n\n在第三个测试用例中，给定的三个点共线。每个叉积均为 $0$，搬迁后也必须为 $0$。因此，Limak 的新屋必须位于经过这些点的直线上。由于还必须位于大正方形内部，新可能的位置被限制在某一线段上（排除其他房屋所在的位置）。任何线段的面积均为 $0$。"},{"iden":"input","content":"输入的第一行包含一个整数 $T$（$1 ≤ T ≤ 500$）——测试用例的数量。接下来是各测试用例的描述。每个测试用例的第一行包含一个整数 $n$（$3 ≤ n ≤ 200 000$）——房屋的数量。接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$-10^6 ≤ x_i, y_i ≤ 10^6$）——第 $i$ 座房屋的坐标。同一测试用例中，没有两座房屋位于同一点。Limak 住在第一座房屋中。所有测试用例的 $n$ 之和不超过 $200 000$。"},{"iden":"output","content":"请输出一个实数，表示 Limak 新屋所有可能放置位置的点集面积。你的答案若绝对误差或相对误差不超过 $10^{-6}$，则被视为正确。更精确地说，设评判程序的答案为 $b$，你的答案为 $a$，则当且仅当 $\\frac{|a - b|}{\\max(1, |b|)} \\leq 10^{-6}$ 时，你的答案会被接受。"},{"iden":"note","content":"在样例测试中，共有 $4$ 个测试用例。在第一个测试用例中，有四座房屋，Limak 的房屋位于 $(5, 3)$。合法的新位置构成一个三角形，其顶点为 $(0, 1)$、$(10, 1)$ 和 $(3, 51)$，但不包含边界。该三角形的面积为 $250$。在第二个测试用例中，合法的新位置构成一个宽为 $50 000$、高为 $2 000 000$ 的矩形。别忘了新位置必须位于代表 Bearland 的大正方形内部。在第三个测试用例中，给定的三个点共线。每个叉积均为 $0$，搬迁后也必须为 $0$。因此，Limak 的新屋必须位于经过这些点的直线上。由于还必须位于大正方形内部，新可能的位置被限制在某一线段上（排除其他房屋所在的位置）。任何线段的面积均为 $0$。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of houses.  \nLet $ P = \\{p_1, p_2, \\dots, p_n\\} \\subset \\mathbb{R}^2 $ be the set of house locations, with $ p_i = (x_i, y_i) $, and $ p_1 $ is Limak’s current house.  \nLet $ S = [-10^6, 10^6]^2 \\subset \\mathbb{R}^2 $ be Bearland (area $ |S| = 4 \\cdot 10^{12} $).\n\nFor any three points $ p_i, p_j, p_k \\in P $, define the cross product:  \n$$\n(p_j - p_i) \\times (p_k - p_i) = (x_j - x_i)(y_k - y_i) - (y_j - y_i)(x_k - x_i)\n$$\n\nLet $ C = \\{ (i,j,k) \\in \\{1,\\dots,n\\}^3 \\} $ be the set of all ordered triples.\n\n**Constraints**  \n1. $ 3 \\leq n \\leq 200{,}000 $  \n2. $ p_i \\ne p_j $ for $ i \\ne j $  \n3. The new house location $ q \\in S \\setminus \\{p_2, \\dots, p_n\\} $  \n4. For all $ (i,j,k) \\in C $, the sign of $ (p_j - p_i) \\times (p_k - p_i) $ must equal the sign of $ (p_j - p_i) \\times (q - p_i) $ if $ i = 1 $, and unchanged otherwise.  \n   - Specifically, for all $ j,k \\in \\{1,\\dots,n\\} $, the sign of $ (p_j - p_1) \\times (p_k - p_1) $ must equal the sign of $ (p_j - q) \\times (p_k - q) $.  \n   - For all $ i \\ne 1 $, and all $ j,k $, the sign of $ (p_j - p_i) \\times (p_k - p_i) $ remains unchanged under replacement of $ p_1 $ by $ q $.\n\n**Objective**  \nCompute the area of the set:  \n$$\nQ = \\left\\{ q \\in S \\setminus \\{p_2, \\dots, p_n\\} \\ \\middle| \\ \\forall j,k \\in \\{1,\\dots,n\\}, \\ \\mathrm{sign}\\left( (p_j - p_1) \\times (p_k - p_1) \\right) = \\mathrm{sign}\\left( (p_j - q) \\times (p_k - q) \\right) \\right\\}\n$$\n\nOutput: $ \\mathrm{Area}(Q) $","simple_statement":null,"has_page_source":false}