English · Original
Chinese · Translation
Formal · Original
Cowboy Beblop is a funny little boy who likes sitting at his computer. He somehow obtained two elastic hoops in the shape of 2D polygons, which are not necessarily convex. Since there's no gravity on his spaceship, the hoops are standing still in the air. Since the hoops are very elastic, Cowboy Beblop can stretch, rotate, translate or shorten their edges as much as he wants.
For both hoops, you are given the number of their vertices, as well as the position of each vertex, defined by the X , Y and Z coordinates. The vertices are given in the order they're connected: the 1st vertex is connected to the 2nd, which is connected to the 3rd, etc., and the last vertex is connected to the first one. Two hoops are connected if it's impossible to pull them to infinity in different directions by manipulating their edges, without having their edges or vertices intersect at any point – **just like when two links of a chain are connected**. **The polygons' edges do not intersect or overlap**.
To make things easier, we say that two polygons are **well-connected**, if the edges of one polygon cross the area of the other polygon in two different directions (from the upper and lower sides of the plane defined by that polygon) a different number of times.
Cowboy Beblop is fascinated with the hoops he has obtained and he would like to know whether they are well-connected or not. Since he’s busy playing with his dog, Zwei, he’d like you to figure it out for him. He promised you some sweets if you help him!
## Input
The first line of input contains an integer _n_ (3 ≤ _n_ ≤ 100 000), which denotes the number of edges of the first polygon. The next N lines each contain the integers _x_, _y_ and _z_ ( - 1 000 000 ≤ _x_, _y_, _z_ ≤ 1 000 000) — coordinates of the vertices, in the manner mentioned above. The next line contains an integer _m_ (3 ≤ _m_ ≤ 100 000) , denoting the number of edges of the second polygon, followed by _m_ lines containing the coordinates of the second polygon’s vertices.
It is guaranteed that both polygons are simple (no self-intersections), and in general that **the obtained polygonal lines do not intersect each other**. Also, you can assume that no 3 consecutive points of a polygon lie on the same line.
## Output
Your output should contain only one line, with the words "_YES_" or "_NO_", depending on whether the two given polygons are well-connected.
[samples]
## Note
On the picture below, the two polygons are well-connected, as the edges of the vertical polygon cross the area of the horizontal one exactly once in one direction (for example, from above to below), and zero times in the other (in this case, from below to above). Note that the polygons do not have to be parallel to any of the xy-,xz-,yz- planes in general. 
[{"iden":"statement","content":"Cowboy Beblop 是一个有趣的小男孩，喜欢坐在电脑前。他不知怎么得到了两个呈二维多边形形状的弹性环，这些多边形不一定是凸的。由于他的飞船上没有重力，这两个环静止在空中。由于环非常有弹性，Cowboy Beblop 可以任意拉伸、旋转、平移或缩短它们的边。\n\n对于两个环，你都得到了它们的顶点数量以及每个顶点的位置（由 X、Y 和 Z 坐标定义）。顶点按连接顺序给出：第 1 个顶点连接到第 2 个，第 2 个连接到第 3 个，依此类推，最后一个顶点连接回第一个顶点。两个环是连接的，当且仅当无法通过操纵它们的边（在任何时刻都不允许边或顶点相交）将它们拉向无穷远的不同方向——*就像链条的两个链环相互连接一样*。*多边形的边不会相交或重叠*。\n\n为了简化问题，我们说两个多边形是*良好连接*的，当且仅当一个多项式的边在另一个多边形定义的平面的上下两侧交叉的次数不同。\n\nCowboy Beblop 对他得到的环非常着迷，他想知道它们是否是良好连接的。由于他正忙着和他的狗 Zwei 玩耍，他希望你能帮他解决这个问题。他答应给你一些糖果作为回报！\n\n输入的第一行包含一个整数 #cf_span[n] (#cf_span[3 ≤ n ≤ 100 000])，表示第一个多边形的边数。接下来的 N 行每行包含三个整数 #cf_span[x]、#cf_span[y] 和 #cf_span[z] (#cf_span[ - 1 000 000 ≤ x, y, z ≤ 1 000 000]) —— 按上述方式给出的顶点坐标。下一行包含一个整数 #cf_span[m] (#cf_span[3 ≤ m ≤ 100 000])，表示第二个多边形的边数，接着是 #cf_span[m] 行，每行包含第二个多边形顶点的坐标。\n\n保证两个多边形都是简单的（无自交），且一般情况下*得到的多边形线不相交*。此外，你可以假设一个多边形中任意三个连续点不共线。\n\n你的输出应仅包含一行，根据两个给定多边形是否良好连接，输出 \"_YES_\" 或 \"_NO_\"。\n\n在下图中，两个多边形是良好连接的，因为垂直多边形的边恰好一次从一个方向穿过水平多边形的区域（例如从上到下），而在另一个方向（从下到上）穿过零次。注意，多边形通常不需要与 xy、xz 或 yz 平面平行。"},{"iden":"input","content":"The first line of input contains an integer #cf_span[n] (#cf_span[3 ≤ n ≤ 100 000]), which denotes the number of edges of the first polygon. The next N lines each contain the integers #cf_span[x], #cf_span[y] and #cf_span[z] (#cf_span[ - 1 000 000 ≤ x, y, z ≤ 1 000 000]) — coordinates of the vertices, in the manner mentioned above. The next line contains an integer #cf_span[m] (#cf_span[3 ≤ m ≤ 100 000]) , denoting the number of edges of the second polygon, followed by #cf_span[m] lines containing the coordinates of the second polygon’s vertices.It is guaranteed that both polygons are simple (no self-intersections), and in general that *the obtained polygonal lines do not intersect each other*. Also, you can assume that no 3 consecutive points of a polygon lie on the same line."},{"iden":"output","content":"Your output should contain only one line, with the words \"_YES_\" or \"_NO_\", depending on whether the two given polygons are well-connected. "},{"iden":"note","content":"On the picture below, the two polygons are well-connected, as the edges of the vertical polygon cross the area of the horizontal one exactly once in one direction (for example, from above to below), and zero times in the other (in this case, from below to above). Note that the polygons do not have to be parallel to any of the xy-,xz-,yz- planes in general. "}]"
Let $ P $ and $ Q $ be two simple 3D polygons with $ n $ and $ m $ vertices respectively, given as ordered sequences of points in $ \mathbb{R}^3 $, with edges connecting consecutive vertices (and the last to the first). The polygons are non-intersecting and non-overlapping.
Define for polygon $ P $ its **oriented plane** $ \pi_P $ as the plane containing $ P $, with normal vector $ \vec{N}_P $ computed via the cross product of two consecutive edge vectors (e.g., $ \vec{v}_1 = p_2 - p_1 $, $ \vec{v}_2 = p_3 - p_2 $, then $ \vec{N}_P = \vec{v}_1 \times \vec{v}_2 $), normalized to point consistently (e.g., right-hand rule from vertex order).
For each edge $ e = (q_i, q_{i+1}) $ of polygon $ Q $, compute the number of times $ e $ intersects the **infinite plane** $ \pi_P $, and determine the **sign of the crossing** relative to $ \vec{N}_P $:
- Let $ t \in \mathbb{R} $ be the parameter such that $ q_i + t(q_{i+1} - q_i) \in \pi_P $, if it exists.
- If $ t \in (0,1) $, then edge $ e $ intersects $ \pi_P $ at an interior point.
- Compute the scalar projection of the vector $ q_{i+1} - q_i $ onto $ \vec{N}_P $:
$$
s = \frac{(q_{i+1} - q_i) \cdot \vec{N}_P}{\|\vec{N}_P\|}
$$
- If $ s > 0 $, the edge crosses $ \pi_P $ **from below to above** (relative to $ \vec{N}_P $).
- If $ s < 0 $, the edge crosses $ \pi_P $ **from above to below**.
Let:
- $ C_{Q \to P}^+ $ = number of edges of $ Q $ crossing $ \pi_P $ from below to above,
- $ C_{Q \to P}^- $ = number of edges of $ Q $ crossing $ \pi_P $ from above to below.
Similarly, define $ C_{P \to Q}^+ $ and $ C_{P \to Q}^- $ for edges of $ P $ crossing the plane $ \pi_Q $ of polygon $ Q $, using $ \vec{N}_Q $ as the normal.
**Definition**: $ P $ and $ Q $ are **well-connected** if and only if:
$$
|C_{Q \to P}^+ - C_{Q \to P}^-| = 1 \quad \text{and} \quad |C_{P \to Q}^+ - C_{P \to Q}^-| = 1
$$
Output "YES" if the above holds; otherwise, output "NO".
API Response (JSON)
{
"problem": {
"name": "I. Cowboy Beblop at his computer",
"description": {
"content": "Cowboy Beblop is a funny little boy who likes sitting at his computer. He somehow obtained two elastic hoops in the shape of 2D polygons, which are not necessarily convex. Since there's no gravity on ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF717I"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Cowboy Beblop is a funny little boy who likes sitting at his computer. He somehow obtained two elastic hoops in the shape of 2D polygons, which are not necessarily convex. Since there's no gravity on ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"Cowboy Beblop 是一个有趣的小男孩，喜欢坐在电脑前。他不知怎么得到了两个呈二维多边形形状的弹性环，这些多边形不一定是凸的。由于他的飞船上没有重力，这两个环静止在空中。由于环非常有弹性，Cowboy Beblop 可以任意拉伸、旋转、平移或缩短它们的边。\\n\\n对于两个环，你都得到了它们的顶点数量以及每个顶点的位置（由 X、...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ P $ and $ Q $ be two simple 3D polygons with $ n $ and $ m $ vertices respectively, given as ordered sequences of points in $ \\mathbb{R}^3 $, with edges connecting consecutive vertices (and the ...",
"is_translate": false,
"language": "Formal"
}
]
}