Hide

Problem M
Triangular Clouds

/problems/triangularclouds/file/statement/en/img-0001.jpg
Photo by SketchUp

Garry is looking at the sky. Such a beautiful day! He notices that the clouds are particularly beautiful today, and wishes to record the current state of the sky. He has no camera, so he begins writing down coordinate points. Fortunately for Garry, the current cloud cover can be represented as the union of non-intersecting, non-degenerate triangles where each vertex is at a coordinate point on the $xy$-plane. Two triangles are considered non-intersecting if their intersection has area $0$. A triangle is degenerate if its area is $0$.

The next day, Garry’s friend Jerry goes to look at the sky. Jerry also wishes to record the current state of the sky. He follows the same protocol as Garry, and writes down the cloud cover as a set of non-intersecting triangles.

Garry and Jerry want to determine if they saw the same cloud cover. Unfortunately, there are multiple possible ways to represent the same cloud cover! Given Garry and Jerry’s notes, did they see the same cloud cover in the sky?

Input

The first line of input contains the integer $n$, $(0 \le n \le 100\, 000)$, the number of triangles Garry wrote down. Each of the next $n$ lines contains $6$ space separated integers, $x_1$, $y_1$, $x_2$, $y_2$, $x_3$, and $y_3$. These are Garry’s triangles. The next line contains the integer $m$, $(0 \le m \le 100\, 000)$, the number of triangles Jerry wrote down. Each of the next $m$ lines contains $6$ space separated integers, $x_1$, $y_1$, $x_2$, $y_2$, $x_3$, and $y_3$. These are Jerry’s triangles. The absolute value of the $x$ and $y$ coordinates are at most $10^9$. (That’s as far as Garry and Jerry can see.)

Output

Print “yes” if Garry and Jerry saw the same cloud cover, or “no” if they did not.

Sample Input 1 Sample Output 1
1
10000 0 10000 10000 0 10000
3
10000 0 10000 10000 5000 5000
5000 5000 10000 10000 0 10000
0 0 0 1000 1000 0
no
Sample Input 2 Sample Output 2
2
9996 0 9997 0 0 1
9999 0 10000 0 0 1
2
9997 0 9998 0 0 1
9998 0 9999 0 0 1
no
Sample Input 3 Sample Output 3
1
2 0 2 4 4 2
2
2 0 2 2 4 2
2 2 4 2 2 4
yes

Please log in to submit a solution to this problem

Log in