G. Cut the pie

Codeforces

IDCF799G

Time3000ms

Memory256MB

Difficulty—

binary searchdata structuresgeometry

English · Original

Chinese · Translation

Formal · Original

Arkady reached the _n_\-th level in Township game, so Masha decided to bake a pie for him! Of course, the pie has a shape of convex _n_\-gon, i.e. a polygon with _n_ vertices. Arkady decided to cut the pie in two equal in area parts by cutting it by a straight line, so that he can eat one of them and give the other to Masha. There is a difficulty because Arkady has already put a knife at some point of the pie, so he now has to cut the pie by a straight line passing trough this point. Help Arkady: find a line that passes through the point Arkady has put a knife into and cuts the pie into two parts of equal area, or determine that it's impossible. Your program has to quickly answer many queries with the same pie, but different points in which Arkady puts a knife. ## Input The first line contains two integers _n_ and _q_ (3 ≤ _n_ ≤ 104, 1 ≤ _q_ ≤ 105) — the number of vertices in the pie and the number of queries. _n_ line follow describing the polygon vertices in clockwise order. The _i_\-th of these line contains two integers _x__i_ and _y__i_ ( - 106 ≤ _x__i_, _y__i_ ≤ 106) — the coordinates of the _i_\-th vertex. It is guaranteed that the polygon is strictly convex, in particular, no three vertices line on the same line. An empty line follows. _q_ lines follow describing the query points. The _i_\-th of these lines contain two integers _x__i_ and _y__i_ ( - 106 ≤ _x__i_, _y__i_ ≤ 106) — the coordinates of the point in which Arkady puts the knife in the _i_\-th query. In is guaranteed that in each query the given point is strictly inside the polygon, in particular, is not on its edges. ## Output For each query print single integer — the polar angle of the line that is the answer for the corresponding query, in radians. The angle should be in the segment \[0;π\], the angles are measured from the direction of _OX_ axis in counter-clockwise order. For example, the polar angle of the _OY_ axis is . If there is no answer in that query, print _\-1_. If there are several answers, print any of them. Your answer is considered correct if the difference between the areas of the parts divided by the total area of the polygon doesn't exceed 10 - 4 by absolute value. In other words, if _a_ and _b_ are the areas of the parts after the cut, then your answer is correct if and only of . [samples]

Arkady 在 Township 游戏中达到了第 #cf_span[n] 级，因此 Masha 决定为他烤一个派！当然，这个派的形状是一个凸 #cf_span[n] 边形，即一个具有 #cf_span[n] 个顶点的多边形。 Arkady 决定用一条直线将派切成两个面积相等的部分，以便他吃掉其中一部分，另一部分给 Masha。但有一个困难：Arkady 已经在派的某一点上放了一把刀，因此他现在必须通过这个点画一条直线来切派。请帮助 Arkady：找出一条通过 Arkady 放刀的点、并将派切成两个面积相等部分的直线，或者判断这是不可能的。你的程序需要快速回答多个关于同一个派但不同放刀点的查询。第一行包含两个整数 #cf_span[n] 和 #cf_span[q] (#cf_span[3 ≤ n ≤ 104], #cf_span[1 ≤ q ≤ 105]) —— 派的顶点数和查询次数。接下来 #cf_span[n] 行描述多边形的顶点，按顺时针顺序排列。第 #cf_span[i] 行包含两个整数 #cf_span[xi] 和 #cf_span[yi] (#cf_span[ - 106 ≤ xi, yi ≤ 106]) —— 第 #cf_span[i] 个顶点的坐标。保证该多边形是严格凸的，特别是任意三个顶点不共线。随后是一个空行。接下来 #cf_span[q] 行描述查询点。第 #cf_span[i] 行包含两个整数 #cf_span[xi] 和 #cf_span[yi] (#cf_span[ - 106 ≤ xi, yi ≤ 106]) —— 第 #cf_span[i] 次查询中 Arkady 放刀的点的坐标。保证每个查询中的点严格位于多边形内部，特别是不在其边上。对于每个查询，输出一个整数 —— 对应查询的答案直线的极角（以弧度为单位）。该角度应在区间 #cf_span[[0;π]] 内，角度从 #cf_span[OX] 轴方向逆时针测量。例如，#cf_span[OY] 轴的极角为。如果该查询无解，请输出 _-1_。如果存在多个答案，输出任意一个即可。你的答案被认为是正确的，当且仅当切割后两部分面积之差与多边形总面积的比值的绝对值不超过 #cf_span[10 - 4]。换句话说，如果 #cf_span[a] 和 #cf_span[b] 是切割后的两部分面积，则你的答案正确当且仅当。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[q] (#cf_span[3 ≤ n ≤ 104], #cf_span[1 ≤ q ≤ 105]) —— 派的顶点数和查询次数。接下来 #cf_span[n] 行描述多边形的顶点，按顺时针顺序排列。第 #cf_span[i] 行包含两个整数 #cf_span[xi] 和 #cf_span[yi] (#cf_span[ - 106 ≤ xi, yi ≤ 106]) —— 第 #cf_span[i] 个顶点的坐标。保证该多边形是严格凸的，特别是任意三个顶点不共线。随后是一个空行。接下来 #cf_span[q] 行描述查询点。第 #cf_span[i] 行包含两个整数 #cf_span[xi] 和 #cf_span[yi] (#cf_span[ - 106 ≤ xi, yi ≤ 106]) —— 第 #cf_span[i] 次查询中 Arkady 放刀的点的坐标。保证每个查询中的点严格位于多边形内部，特别是不在其边上。 ## Output 对于每个查询，输出一个整数 —— 对应查询的答案直线的极角（以弧度为单位）。该角度应在区间 #cf_span[[0;π]] 内，角度从 #cf_span[OX] 轴方向逆时针测量。例如，#cf_span[OY] 轴的极角为。如果该查询无解，请输出 _-1_。如果存在多个答案，输出任意一个即可。你的答案被认为是正确的，当且仅当切割后两部分面积之差与多边形总面积的比值的绝对值不超过 #cf_span[10 - 4]。换句话说，如果 #cf_span[a] 和 #cf_span[b] 是切割后的两部分面积，则你的答案正确当且仅当。 [samples]

**Definitions** Let $ P = (v_1, v_2, \dots, v_n) $ be a strictly convex polygon in $ \mathbb{R}^2 $, with vertices $ v_i = (x_i, y_i) $ given in clockwise order. Let $ A_P $ denote the area of $ P $. Let $ Q = \{q_1, q_2, \dots, q_q\} $ be a set of $ q $ query points, where each $ q_j = (x_j, y_j) $ lies strictly inside $ P $. **Constraints** 1. $ 3 \leq n \leq 10^4 $, $ 1 \leq q \leq 10^5 $ 2. $ |x_i|, |y_i| \leq 10^6 $, $ |x_j|, |y_j| \leq 10^6 $ 3. $ P $ is strictly convex; no three vertices are collinear. 4. Each query point $ q_j $ lies in the interior of $ P $. **Objective** For each query point $ q_j $, find a line $ L_j $ passing through $ q_j $ that divides $ P $ into two regions of equal area $ \frac{A_P}{2} $. If such a line exists, output its polar angle $ \theta_j \in [0, \pi] $ (measured counterclockwise from the positive $ x $-axis). If no such line exists, output $ -1 $. The solution must satisfy $ \left| \frac{a - b}{A_P} \right| \leq 10^{-4} $, where $ a, b $ are the areas of the two parts.

Samples

Input #1

Output #1

2.67794504460098710000

Input #2

Output #2

0.60228734612690049000
1.27933953226473580000
2.85805511179015910000

API Response (JSON)

{
  "problem": {
    "name": "G. Cut the pie",
    "description": {
      "content": "Arkady reached the _n_\\-th level in Township game, so Masha decided to bake a pie for him! Of course, the pie has a shape of convex _n_\\-gon, i.e. a polygon with _n_ vertices. Arkady decided to cut t",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF799G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Arkady reached the _n_\\-th level in Township game, so Masha decided to bake a pie for him! Of course, the pie has a shape of convex _n_\\-gon, i.e. a polygon with _n_ vertices.\n\nArkady decided to cut t...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Arkady 在 Township 游戏中达到了第 #cf_span[n] 级，因此 Masha 决定为他烤一个派！当然，这个派的形状是一个凸 #cf_span[n] 边形，即一个具有 #cf_span[n] 个顶点的多边形。\n\nArkady 决定用一条直线将派切成两个面积相等的部分，以便他吃掉其中一部分，另一部分给 Masha。但有一个困难：Arkady 已经在派的某一点上放了一把刀，因此他现在...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ P = (v_1, v_2, \\dots, v_n) $ be a strictly convex polygon in $ \\mathbb{R}^2 $, with vertices $ v_i = (x_i, y_i) $ given in clockwise order.  \nLet $ A_P $ denote the area of $ P...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments