CF717I 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$ 个点有一条线段相连。
保证给出的多边形是简单多边形,即不会自交;保证两个多边形之间没有交点。
输出格式
Your output should contain only one line, with the words "YES" or "NO", depending on whether the two given polygons are well-connected.
说明/提示
$3 \leq n , m \leq 100000$,$0 \leq |x| , |y| , |z| \leq 10^6$