Back
Close

Ibrohim and his computer

Statement
Cowboy Beblop is a funny little boy who likes to sit at a computer. From somewhere he got two elastic hoops in the form of two-dimensional polygons, not necessarily convex. Since there is no gravity on his spaceship, the hoops calmly hang in the air (in three-dimensional space). Since the hoops are very elastic, Beblop can stretch them, rotate, move or shorten their ribs as much as they want. For both hoops, you are given the number of vertices and the coordinates of each vertex, determined by the three numbers x, y, and z. The vertices are given in the traversal order: vertex 1 is connected to vertex 2, vertex 2 is connected to vertex 3, and so on, the last vertex is again connected to the first. Two hoops are considered geared if it is impossible to part them to an infinitely large distance only by changing the lengths of the edges and moving them, but not crossing along either the segments or the vertices - just like two chains. Initially, the edges of the polygons do not intersect and do not touch. For simplicity, we say that two polygons are strongly geared if the edges of one of the polygons intersect the area of ​​the other in two different directions (from top to bottom and from bottom to top in the plane defined by this polygon) a different number of times. Cowboy Beblop adores his hoops and would like to know if they are tightly geared or not. Since he is busy playing with his dog, he asks you to determine the answer.

Input description
The first line of the input contains an integer n (3 ≤ n ≤ 100 000) - the number of sides in the first polygon. Each of the next n lines contains three integers x, y and z (- 1 000 000 ≤ x, y, z ≤ 1 000 000) - the coordinates of the vertices in the traversal order. The next line contains the number m (3 ≤ m ≤ 100,000) - the number of vertices in the second rectangle, followed by m lines describing the vertices in the same format as the first rectangle. It is guaranteed that both rectangles do not contain self-intersections and that the corresponding polygons do not intersect and do not touch. It is additionally guaranteed that no three consecutive vertices of the same polygon lie on one straight line.

Output description
Print "YES" or "NO", depending on whether the two polygons are strongly geared or not.

Constraints

Game modes
Fastest

Test cases
Test 1 Test
Input
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
Output
YES

Test 2 Validator
Input
4 4 -2 0 4 3 0 -3 3 0 -3 -2 0 4 6 -2 0 3 2 2 -3 7 0 3 4 6
Output
NO

Test 3 Test
Input
4 -10 5 0 25 18 0 23 8 0 -9 0 0 5 7 12 -5 7 0 -10 7 3 8 7 10 7 7 6 0
Output
YES

Test 4 Validator
Input
8 0 1000 0 436 1013 0 500 500 0 1000 500 0 1000 1000 0 1401 1000 0 1500 0 0 0 0 0 8 -200 1000 400 150 1000 400 125 250 -500 850 250 -500 750 1000 400 1200 1000 400 1250 0 -800 -250 0 -800
Output
YES

Test 5 Test
Input
9 2564 865 0 573 1115 0 -600 1000 0 100 600 0 949 665 0 2341 -2375 0 3879 -561 0 2200 -600 0 2543 -250 0 10 2900 -1000 0 280 60 900 1990 -480 0 1710 -320 0 830 450 -550 660 280 0 270 260 500 345 460 0 -520 1440 -1000 1300 400 -1000
Output
NO

Test 6 Validator
Input
16 0 1000 0 436 1013 0 500 500 0 1000 500 0 1000 1000 0 1401 1028 0 1434 461 0 2087 442 0 2066 1040 0 2492 1031 0 2541 449 0 3069 451 0 3050 1071 0 3702 1071 0 3754 0 0 0 0 0 16 -243 700 394 109 700 365 129 700 -366 763 700 -366 725 700 397 1131 700 409 1173 700 -339 1910 700 -405 1834 700 414 2254 700 439 2323 700 -425 2847 700 -380 2849 700 477 3418 700 470 3537 700 -1057 -294 700 -777
Output
YES

Test 7 Test
Input
100000 0 0 0 0 10 0 2 10 0 2 5 0 4 5 0 4 10 0 6 10 0 6 5 0 8 5 0 8 10 0 10 10 0 10 5 0 12 5 0 12 10 0 14 10 0 14 5 0 16 5 0 16 10 0 18 10 0 18 5 0 20 5 0 20 10 0 22 10 0 22 5 0 24 5 0 24 10 0 26 10 0 26 5 0 28 5 0 28 10 0 30 10 0 30 5 0 32 5 0 32 10 0 34 10 0 34 5 0 36 5 0 36 10 0 38 10 0 38 5 0 40 5 0 40 10 0 42 10 0 42 5 0 44 5 0 44 10 0 46 10 0 46 5 0 48 5 0 48 10 0 50 10 0 50 5 0 52 5 0 52 10 0 54 10 0 54 5 0 56 5 0 56 10 0 58 10 0 58 5 0 60 ...
Output
NO

Test 8 Validator
Input
200 -16171 -15493 -453 -17103 -17040 -453 -8369 -9081 -453 -16694 -18696 -453 -16214 -19041 -453 -14474 -18419 -453 -12692 -16768 -453 -14762 -21403 -453 -10091 -15370 -453 -13204 -22115 -453 -16685 -29505 -453 -15565 -30439 -453 -12635 -27500 -453 -7951 -18704 -453 -10362 -26787 -453 -6552 -18810 -453 -7955 -25971 -453 -6101 -22180 -453 -4604 -17767 -453 -5712 -24347 -453 -4877 -22947 -453 -3268 -19295 -453 -3918 -26142 -453 -2369 -17180 -453 -2685 -28626 -453 -1236 -18311 -453 ...
Output
NO

Solution language

Solution

Stub generator input
codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants