← 返回题目列表

Codeforces · 717/I

I. 牛仔贝布洛普在他的电脑前

中文机器翻译题面 查看原题

牛仔贝布洛普是一个有趣的小男孩,喜欢坐在电脑前。他以某种方式获得了两个二维多边形形状的弹性环,它们不一定是凸的。由于他的宇宙飞船上没有重力,所以圆环静止在空中。由于圆环非常有弹性,牛仔贝布洛普可以根据需要拉伸、旋转、平移或缩短它们的边缘。

对于两个环,您都会获得它们的顶点数以及每个顶点的位置,由 X 、 Y 和 Z 坐标定义。顶点按照它们连接的顺序给出:第一个顶点连接到第二个顶点,第二个顶点连接到第三个顶点,依此类推,最后一个顶点连接到第一个顶点。如果无法通过操纵它们的边缘将两个环向不同方向拉至无穷大,并且它们的边缘或顶点不在任何点相交,则两个环是连接的 - 就像连接链条的两个链接一样。多边形的边不相交或重叠。

为了让事情变得更简单,如果一个多边形的边在两个不同的方向(从该多边形定义的平面的上边和下边)与另一个多边形的区域相交不同的次数,我们就说两个多边形是良好连接的。

牛仔贝布洛普对他获得的圈圈很着迷,他想知道它们是否有良好的联系。因为他正忙着和他的狗 Zwei 玩耍,所以他希望你帮他解决这个问题。他答应给你一些糖果,如果你帮助他!

输入

输入的第一行包含一个整数n (3 ≤ n ≤ 100 000),表示第一个多边形的边数。接下来的 N 行每行包含整数 x、y 和 z (- 1 000 000 ≤ x, y, z ≤ 1 000 000)——顶点的坐标,按照上面提到的方式。下一行包含一个整数 m (3 ≤ m ≤ 100 000) ,表示第二个多边形的边数,后面的 m 行包含第二个多边形顶点的坐标。

保证两个多边形都是简单的(无自交),并且一般情况下获得的折线彼此不相交。另外,您可以假设多边形的 3 个连续点不位于同一条线上。

输出

您的输出应仅包含一行,其中包含“YES”或“NO”一词,具体取决于两个给定的多边形是否连接良好。

示例

输入 #1

4
0 0 0
2 0 0
2 2 0
0 2 0
4
1 1 -1
1 1 1
1 3 1
1 3 -1

输出 #1

YES

注意

在下图中,两个多边形连接良好,因为垂直多边形的边在一个方向(例如,从上到下)与水平多边形的区域恰好相交一次,而在另一个方向上相交零次(在本例中,从下到上)。请注意,多边形通常不必平行于任何 xy、xz、yz 平面。