{"problem":{"name":"E. Satellites","description":{"content":"Real Cosmic Communications is the largest telecommunication company on a far far away planet, located at the very edge of the universe. RCC launches communication satellites. The planet is at the ver","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF856E"},"statements":[{"statement_type":"Markdown","content":"Real Cosmic Communications is the largest telecommunication company on a far far away planet, located at the very edge of the universe. RCC launches communication satellites.\n\nThe planet is at the very edge of the universe, so its form is half of a circle. Its radius is _r_, the ends of its diameter are points _A_ and _B_. The line _AB_ is the edge of the universe, so one of the half-planes contains nothing, neither the planet, nor RCC satellites, nor anything else. Let us introduce coordinates in the following way: the origin is at the center of _AB_ segment, _OX_ axis coincides with line _AB_, the planet is completely in _y_ > 0 half-plane.\n\nThe satellite can be in any point of the universe, except the planet points. Satellites are never located beyond the edge of the universe, nor on the edge itself — that is, they have coordinate _y_ > 0. Satellite antennas are directed in such way that they cover the angle with the vertex in the satellite, and edges directed to points _A_ and _B_. Let us call this area the satellite coverage area.\n\nThe picture below shows coordinate system and coverage area of a satellite.\n\nWhen RCC was founded there were no satellites around the planet. Since then there have been several events of one of the following types:\n\n1. _1 x y_ — launch the new satellite and put it to the point (_x_, _y_). Satellites never move and stay at the point they were launched. Let us assign the number _i_ to the _i_\\-th satellite in order of launching, starting from one.\n2. _2 i_ — remove satellite number _i_.\n3. _3 i j_ — make an attempt to create a communication channel between satellites _i_ and _j_. To create a communication channel a repeater is required. It must not be located inside the planet, but can be located at its half-circle border, or above it. Repeater must be in coverage area of both satellites _i_ and _j_. To avoid signal interference, it must not be located in coverage area of any other satellite. Of course, the repeater must be within the universe, it must have a coordinate _y_ > 0.\n\nFor each attempt to create a communication channel you must find out whether it is possible.\n\nSample test has the following satellites locations:\n\n\n\n## Input\n\nThe first line of input data contains integers _r_ and _n_ — radius of the planet and the number of events (1 ≤ _r_ ≤ 109, 1 ≤ _n_ ≤ 5·105).\n\nEach of the following _n_ lines describe events in the specified format.\n\nSatellite coordinates are integer, the satisfy the following constraints |_x_| ≤ 109, 0 < _y_ ≤ 109. No two satellites that simultaneously exist can occupy the same point. Distance from each satellite to the center of the planet is strictly greater than _r_.\n\nIt is guaranteed that events of types 2 and 3 only refer to satellites that exist at the moment. For all events of type 3 the inequality _i_ ≠ _j_ is satisfied.\n\n## Output\n\nFor each event of type 3 print «_YES_» on a separate line, if it is possible to create a communication channel, or «_NO_» if it is impossible.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Real Cosmic Communications 是位于宇宙最边缘的一颗遥远星球上最大的电信公司。RCC 发射通信卫星。\n\n这颗星球位于宇宙的边缘，因此其形状是半个圆。其半径为 $r$，直径的两端为点 $A$ 和 $B$。直线 $AB$ 是宇宙的边界，因此其中一个半平面不包含任何东西——既没有星球，也没有 RCC 卫星，更没有其他任何事物。我们按如下方式建立坐标系：原点位于线段 $AB$ 的中心，$OX$ 轴与直线 $AB$ 重合，星球完全位于 $y > 0$ 的半平面内。\n\n卫星可以位于宇宙中的任意一点，但不能位于星球上。卫星永远不会位于宇宙边界之外或边界上——即它们的坐标满足 $y > 0$。卫星天线的朝向使得它们覆盖一个以卫星为顶点、两边分别指向点 $A$ 和 $B$ 的角。我们将这一区域称为卫星的 $\\text{coverage area}$（覆盖区域）。\n\n下图展示了坐标系和一个卫星的覆盖区域。\n\n当 RCC 成立时，星球周围没有卫星。从那时起，发生了以下几种类型的事件：\n\n对于每次尝试建立通信信道，你必须判断是否可能实现。\n\n样例测试用例中的卫星位置如下：\n\n输入数据的第一行包含整数 $r$ 和 $n$ —— 星球的半径和事件数量（$1 ≤ r ≤ 10^9$，$1 ≤ n ≤ 5·10^5$）。\n\n接下来的 $n$ 行每行描述一个事件，格式如上所述。\n\n卫星的坐标为整数，满足以下约束：$|x| ≤ 10^9$，$0 < y ≤ 10^9$。同时存在的任意两个卫星不会占据同一个点。每个卫星到星球中心的距离严格大于 $r$。\n\n保证类型为 $2$ 和 $3$ 的事件仅涉及当前存在的卫星。对于所有类型为 $3$ 的事件，满足 $i ≠ j$。\n\n对于每个类型为 $3$ 的事件，如果可以建立通信信道，则在单独一行输出 «_YES_»；否则输出 «_NO_»。\n\n## Input\n\n输入数据的第一行包含整数 $r$ 和 $n$ —— 星球的半径和事件数量（$1 ≤ r ≤ 10^9$，$1 ≤ n ≤ 5·10^5$）。接下来的 $n$ 行每行描述一个事件，格式如上所述。卫星的坐标为整数，满足以下约束：$|x| ≤ 10^9$，$0 < y ≤ 10^9$。同时存在的任意两个卫星不会占据同一个点。每个卫星到星球中心的距离严格大于 $r$。保证类型为 $2$ 和 $3$ 的事件仅涉及当前存在的卫星。对于所有类型为 $3$ 的事件，满足 $i ≠ j$。\n\n## Output\n\n对于每个类型为 $3$ 的事件，如果可以建立通信信道，则在单独一行输出 «_YES_»；否则输出 «_NO_»。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions:**\n\n- Let the planet be the upper semicircle of radius $ r $, centered at the origin $ O = (0, 0) $, with diameter endpoints $ A = (-r, 0) $, $ B = (r, 0) $. The planet occupies the set $ \\{(x, y) \\mid x^2 + y^2 \\leq r^2, y \\geq 0\\} $.\n- Satellites are points $ S = (x, y) \\in \\mathbb{R}^2 $ such that $ y > 0 $ and $ x^2 + y^2 > r^2 $.\n- The **coverage area** of a satellite at $ S = (x, y) $ is the set of points in the plane visible from $ S $ within the angle $ \\angle ASB $, i.e., the conical region bounded by rays $ \\overrightarrow{SA} $ and $ \\overrightarrow{SB} $.\n\n**Given:**\n\n- Initial set of satellites: empty.\n- $ n $ events of three types:\n 1. **Type 1**: Add a satellite at point $ (x, y) $, with integer coordinates satisfying $ y > 0 $, $ x^2 + y^2 > r^2 $.\n 2. **Type 2**: Remove the satellite added at the $ i $-th event (among all previous events of type 1).\n 3. **Type 3**: Given two existing satellites $ i $ and $ j $, determine whether their coverage areas **intersect**.\n\n**Objective:**\n\nFor each type-3 event, output \"YES\" if the coverage areas of the two satellites intersect; \"NO\" otherwise.\n\n---\n\n**Mathematical Formulation:**\n\nLet $ S_i = (x_i, y_i) $, $ S_j = (x_j, y_j) $ be two satellite positions.\n\nDefine the **coverage cone** of a satellite $ S = (x, y) $ as the set of points in the plane lying within the angle $ \\angle ASB $, i.e., the convex cone with apex at $ S $, bounded by the two rays $ \\overrightarrow{SA} $ and $ \\overrightarrow{SB} $.\n\nThe coverage area of $ S $ is the **infinite wedge**:\n\n$$\nC(S) = \\left\\{ P \\in \\mathbb{R}^2 \\mid P \\text{ lies in the interior of } \\angle ASB \\right\\}\n$$\n\nThis wedge can be characterized by the two vectors:\n\n- $ \\vec{u} = \\overrightarrow{SA} = (-r - x, -y) $\n- $ \\vec{v} = \\overrightarrow{SB} = (r - x, -y) $\n\nThe coverage area $ C(S) $ is the set of points $ P $ such that the vector $ \\overrightarrow{SP} $ lies in the convex cone spanned by $ \\vec{u} $ and $ \\vec{v} $, i.e., $ \\overrightarrow{SP} = \\alpha \\vec{u} + \\beta \\vec{v} $ for some $ \\alpha, \\beta \\geq 0 $, not both zero.\n\nTwo coverage areas $ C(S_i) $ and $ C(S_j) $ **intersect** if and only if there exists a point $ P \\in \\mathbb{R}^2 $ such that $ P \\in C(S_i) \\cap C(S_j) $.\n\n---\n\n**Key Geometric Insight:**\n\nThe coverage area of a satellite $ S = (x, y) $ is the set of points visible from $ S $ between $ A $ and $ B $. Since both $ A $ and $ B $ lie on the x-axis, and the satellite is above the x-axis, the coverage area is the region **between the two lines** $ SA $ and $ SB $, extending infinitely upward.\n\nThus, the coverage area is the **infinite angular sector** between the two lines $ SA $ and $ SB $, and **does not extend below the satellite**.\n\nTwo such sectors intersect **if and only if** the two angular sectors (defined by their bounding rays) overlap in the plane.\n\nThis occurs if and only if the two wedges have overlapping angular spans when projected onto the unit circle centered at their respective apices — but since the wedges are defined by fixed endpoints $ A $ and $ B $, a better approach is:\n\n> **Two satellites $ S_i $ and $ S_j $ have intersecting coverage areas if and only if the line segment $ S_iS_j $ intersects the segment $ AB $, or one satellite lies within the coverage cone of the other.**\n\nBut a more precise and computationally tractable condition is:\n\n---\n\n**Final Formal Condition (for Type 3 events):**\n\nLet $ S_i = (x_i, y_i) $, $ S_j = (x_j, y_j) $.\n\nDefine the **angular span** of satellite $ S $ as the angle $ \\angle ASB $, and the **directions** from $ S $ to $ A $ and $ B $.\n\nThe coverage areas of $ S_i $ and $ S_j $ intersect **if and only if** the two cones $ C(S_i) $ and $ C(S_j) $ have non-empty intersection.\n\nThis happens **if and only if** the **convex hull** of the four points $ A, B, S_i, S_j $ does **not** separate the two satellites in angular order around the circle.\n\nA more efficient characterization:\n\n> The coverage areas of $ S_i $ and $ S_j $ intersect **if and only if** the line segment $ S_iS_j $ intersects the segment $ AB $, **or** $ S_j $ lies inside the cone $ C(S_i) $, **or** $ S_i $ lies inside the cone $ C(S_j) $.\n\nBut even better: since both cones are defined by rays to the fixed points $ A $ and $ B $, the intersection of two such cones is non-empty **if and only if** the two cones overlap in the angular space around the upper half-plane.\n\nThis reduces to checking whether the **two intervals** of angles (from $ S_i $ and $ S_j $) between $ \\overrightarrow{SA} $ and $ \\overrightarrow{SB} $ **overlap**.\n\nBut since the cones are defined by fixed endpoints $ A $ and $ B $, we can use the following **necessary and sufficient condition**:\n\n---\n\n**Key Theorem (Geometric):**\n\nThe coverage areas of two satellites $ S_i $ and $ S_j $ intersect **if and only if** the **line segment $ S_iS_j $** intersects the **line segment $ AB $**.\n\n**Why?**\n\n- The coverage area of a satellite is the set of points visible from $ S $ within $ \\angle ASB $, i.e., the region bounded by rays $ SA $ and $ SB $.\n- The union of all such coverage areas for all satellites covers the region **above** the planet and **between** the two lines $ SA $ and $ SB $.\n- Two such regions intersect if and only if their defining wedges overlap — which occurs precisely when the line segment connecting the two satellites crosses the diameter $ AB $, because $ AB $ is the \"base\" of both wedges.\n\n**Proof Sketch:**\n\n- If $ S_iS_j $ crosses $ AB $, then the two wedges must overlap in the region around the crossing point.\n- If $ S_iS_j $ does not cross $ AB $, then both satellites lie entirely on one side of the line $ AB $, and since both wedges are bounded by rays to $ A $ and $ B $, their angular spans are disjoint in the upper half-plane.\n\n**Therefore:**\n\n> For a type-3 event with satellites $ i $ and $ j $, the answer is **YES** if and only if the line segment $ S_iS_j $ intersects the segment $ AB $, where $ A = (-r, 0) $, $ B = (r, 0) $.\n\n---\n\n**Final Mathematical Statement:**\n\nLet $ S_i = (x_i, y_i) $, $ S_j = (x_j, y_j) $ be two satellite positions.\n\nLet $ A = (-r, 0) $, $ B = (r, 0) $.\n\nDefine segment $ AB = \\{ (x, 0) \\mid -r \\leq x \\leq r \\} $.\n\nDefine segment $ S_iS_j = \\{ (1-t)S_i + tS_j \\mid t \\in [0,1] \\} $.\n\nThen:\n\n$$\n\\boxed{\n\\text{Answer} = \n\\begin{cases}\n\\text{YES} & \\text{if } S_iS_j \\cap AB \\neq \\emptyset \\\\\n\\text{NO} & \\text{otherwise}\n\\end{cases}\n}\n$$\n\n**Implementation Note:**\n\nTo check if segment $ S_iS_j $ intersects segment $ AB $:\n\n- Since $ AB $ lies on the x-axis from $ (-r, 0) $ to $ (r, 0) $, and both $ S_i, S_j $ have $ y > 0 $, the segments intersect if and only if the line $ S_iS_j $ crosses the x-axis **within** $ [-r, r] $.\n\nThat is:\n\n- Let $ t \\in [0,1] $ be the parameter where $ y(t) = (1-t)y_i + t y_j = 0 $.\n- Solve: $ t = \\frac{y_i}{y_i - y_j} $ (if $ y_i \\ne y_j $).\n- If $ t \\in [0,1] $, then the intersection point is $ x = (1-t)x_i + t x_j $.\n- Check if $ -r \\leq x \\leq r $.\n\nAlternatively, use the **crossing condition**:\n\nThe segment $ S_iS_j $ intersects $ AB $ if and only if:\n\n$$\n(y_i > 0 \\land y_j > 0) \\quad \\text{and} \\quad \\text{the x-intercept of line } S_iS_j \\text{ lies in } [-r, r]\n$$\n\nThe x-intercept $ x_0 $ of line through $ S_i, S_j $ is:\n\n$$\nx_0 = x_i - y_i \\cdot \\frac{x_j - x_i}{y_j - y_i}\n$$\n\nThen:\n\n$$\n\\boxed{\n\\text{YES} \\iff -r \\leq x_0 \\leq r\n}\n$$\n\n(Note: Since $ y_i, y_j > 0 $, the line crosses the x-axis exactly once if $ y_i \\ne y_j $. If $ y_i = y_j $, the line is horizontal and never crosses x-axis → no intersection → NO.)\n\n---\n\n**Summary:**\n\nFor each type-3 event with satellites $ i, j $:\n\n- If $ y_i = y_j $: output \"NO\" (line parallel to AB, no intersection).\n- Else:\n $$\n x_0 = x_i - y_i \\cdot \\frac{x_j - x_i}{y_j - y_i}\n $$\n $$\n \\text{Output \"YES\" if } -r \\leq x_0 \\leq r, \\text{ else \"NO\"}\n $$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF856E","tags":[],"sample_group":[["5 8\n1 -5 8\n1 -4 8\n1 -3 8\n1 2 7\n3 1 3\n2 2\n3 1 3\n3 3 4","NO\nYES\nYES"]],"created_at":"2026-03-03 11:00:39"}}