Cowboy Beblop at his computer

题意翻译

### 题目描述 给定三维空间内的两个**平面多边形**，即每一个给出的多边形上的所有点共面，两个多边形不一定是凸多边形，它们所在的面不一定与 $x,y,z$ 轴垂直。 你需要确定：将其中一个多边形的边按照逆时针顺序定向，其自上而下穿过另一个多边形的次数与自下而上穿过另一个多边形的次数是否相等。 ### 输入格式 第一行一个整数 $n$ 表示第一个平面多边形上的点数，接下来 $n$ 行每行三个整数 $x,y,z$ 表示该多边形上的一点。按照多边形的点的给定顺序，第 $i$ 个点与第 $i \mod n + 1$ 个点有一条线段相连。 第 $n+2$ 行一个整数 $m$ 表示第二个平面多边形上的点数，接下来 $m$ 行每行三个整数 $x,y,z$ 表示该多边形上的一点。按照多边形的点的给定顺序，第 $i$ 个点与第 $i \mod m + 1$ 个点有一条线段相连。 保证给出的多边形是简单多边形，即不会自交；保证两个多边形之间没有交点。 ### 输出格式 如果题目描述中的问题回答为“相等”，输出 `NO`，否则输出 `YES`。 ### 数据范围 $3 \leq n , m \leq 100000$，$0 \leq |x| , |y| , |z| \leq 10^6$

题目描述

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!

输入输出格式

输入格式

The first line of input contains an integer $ n $ ( $ 3<=n<=100000 $ ), which denotes the number of edges of the first polygon. The next N lines each contain the integers $ x $ , $ y $ and $ z $ ( $ -1000000<=x,y,z<=1000000 $ ) — coordinates of the vertices, in the manner mentioned above. The next line contains an integer $ m $ ( $ 3<=m<=100000 $ ) , 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.

输出格式

Your output should contain only one line, with the words "YES" or "NO", depending on whether the two given polygons are well-connected.

输入输出样例

输入样例 #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

说明

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.