E. Double Fence

Codeforces

IDCF10148E

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

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. He 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. Tomask 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. The 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. Output YES if one fence is strictly inside the other (the first fence is strictly inside the second or vice versa). Output NO otherwise. ## Input The 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. ## Output Output YES if one fence is strictly inside the other (the first fence is strictly inside the second or vice versa). Output NO otherwise. [samples]

**Definitions** Let $ 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 $. **Constraints** 1. $ 3 \leq N, M \leq 10^5 $ 2. 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 $ 3. No two vertices are identical within a polygon. 4. Polygons may have collinear consecutive vertices. **Objective** Determine whether one polygon is *strictly contained* inside the other: $$ P \subset \text{int}(Q) \quad \text{or} \quad Q \subset \text{int}(P) $$ Output `YES` if either holds, `NO` otherwise.

API Response (JSON)

{
  "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. Th...",
      "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 ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments