{"problem":{"name":"E. Double Fence","description":{"content":"Danfsk bought some sheep and wants to protect them from wolves. He had the brilliant idea of building two convex fences, one strictly inside the other, and keeping all sheep inside the inner fence. Th","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10148E"},"statements":[{"statement_type":"Markdown","content":"Danfsk bought some sheep and wants to protect them from wolves. He had the brilliant idea of building two convex fences, one strictly inside the other, and keeping all sheep inside the inner fence. This way, the sheep would have a second layer of protection from the wolves.\n\nHe hired Tomask, a famous fence architect, to design two fences for him. After finishing his project, Tomask gave Danfsk two pieces of paper, each containing the coordinates of the poles of a convex fence.\n\nTomask is also famous for miscalculations on his projects, so, before paying Tomask and starting building the fences, Danfsk wants to check if one convex fence is really strictly inside the other in Tomask's project. He asked you to help him with this task.\n\nThe first line of the input contains two integers N and M (3 ≤ N, M ≤ 105) indicating respectively the number of poles of the first convex fence and the number of poles of the second convex fence.\n\nEach of the following N lines contains two integers: the i-th line contains xi1 and yi1 ( - 109 ≤ xi1, yi1 ≤ 109), indicating the coordinates of the i-th pole of the first fence. \n\nEach of the following M lines contains two integers: the i-th line contains xi2 and yi2 ( - 109 ≤ xi2, yi2 ≤ 109), indicating the coordinates of the i-th pole of the second fence.\n\nEach fence has the shape of a convex polygon. Pole coordinates of each fence are given in clockwise order. No two points in the project are the same.\n\nNote that there may be colinear poles in the project.\n\nOutput YES if one fence is strictly inside the other (the first fence is strictly inside the second or vice versa). Output NO otherwise.\n\n## Input\n\nThe first line of the input contains two integers N and M (3 ≤ N, M ≤ 105) indicating respectively the number of poles of the first convex fence and the number of poles of the second convex fence.Each of the following N lines contains two integers: the i-th line contains xi1 and yi1 ( - 109 ≤ xi1, yi1 ≤ 109), indicating the coordinates of the i-th pole of the first fence. Each of the following M lines contains two integers: the i-th line contains xi2 and yi2 ( - 109 ≤ xi2, yi2 ≤ 109), indicating the coordinates of the i-th pole of the second fence.Each fence has the shape of a convex polygon. Pole coordinates of each fence are given in clockwise order. No two points in the project are the same.Note that there may be colinear poles in the project.\n\n## Output\n\nOutput YES if one fence is strictly inside the other (the first fence is strictly inside the second or vice versa). Output NO otherwise.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ P = (p_1, p_2, \\dots, p_N) $ and $ Q = (q_1, q_2, \\dots, q_M) $ be two convex polygons in $ \\mathbb{R}^2 $, given as sequences of vertices in clockwise order, with $ N, M \\geq 3 $.\n\n**Constraints**  \n1. $ 3 \\leq N, M \\leq 10^5 $  \n2. All coordinates are integers: $ p_i = (x_i^1, y_i^1), q_j = (x_j^2, y_j^2) $, with $ -10^9 \\leq x, y \\leq 10^9 $  \n3. No two vertices are identical within a polygon.  \n4. Polygons may have collinear consecutive vertices.\n\n**Objective**  \nDetermine whether one polygon is *strictly contained* inside the other:  \n$$\nP \\subset \\text{int}(Q) \\quad \\text{or} \\quad Q \\subset \\text{int}(P)\n$$  \nOutput `YES` if either holds, `NO` otherwise.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10148E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}