A. Two Squares

Codeforces

IDCF993A

Time1000ms

Memory256MB

Difficulty—

geometryimplementation

English · Original

Chinese · Translation

Formal · Original

You are given two squares, one with sides parallel to the coordinate axes, and another one with sides at 45 degrees to the coordinate axes. Find whether the two squares intersect. The interior of the square is considered to be part of the square, i.e. if one square is completely inside another, they intersect. If the two squares only share one common point, they are also considered to intersect. ## Input The input data consists of two lines, one for each square, both containing 4 pairs of integers. Each pair represents coordinates of one vertex of the square. Coordinates within each line are either in clockwise or counterclockwise order. The first line contains the coordinates of the square with sides parallel to the coordinate axes, the second line contains the coordinates of the square at 45 degrees. All the values are integer and between $-100$ and $100$. ## Output Print "_Yes_" if squares intersect, otherwise print "_No_". You can print each letter in any case (upper or lower). [samples] ## Note In the first example the second square lies entirely within the first square, so they do intersect. In the second sample squares do not have any points in common. Here are images corresponding to the samples: <center>![image](https://espresso.codeforces.com/73ea9d4dacf49c0c31bbb1cb457bba6c0b1e5f57.png)</center><center>![image](https://espresso.codeforces.com/2298f1d19747a4151e08ae09e7102c905c149edc.png)</center><center>![image](https://espresso.codeforces.com/d8ae723351e525099008fa1d205ae694ba9d6974.png)</center>

[{"iden":"statement","content":"给定两个正方形，一个边与坐标轴平行，另一个边与坐标轴成 45 度角。判断这两个正方形是否相交。\n\n正方形的内部被视为正方形的一部分，即如果一个正方形完全包含在另一个正方形内，则它们相交。如果两个正方形仅共享一个公共点，也被认为是相交的。\n\n输入数据包含两行，每行对应一个正方形，每行包含 4 对整数。每对整数表示正方形的一个顶点的坐标。每行内的坐标按顺时针或逆时针顺序排列。\n\n第一行包含边与坐标轴平行的正方形的坐标，第二行包含边与坐标轴成 45 度角的正方形的坐标。\n\n所有值均为介于 $-100$ 和 $100$ 之间的整数。\n\n如果正方形相交，请输出 \"_Yes_\"，否则输出 \"_No_\"。\n\n你可以以任意大小写形式输出每个字母。\n\n在第一个示例中，第二个正方形完全位于第一个正方形内部，因此它们相交。\n\n在第二个示例中，两个正方形没有任何公共点。\n\n以下是对应示例的图像：\n\n"},{"iden":"input","content":"输入数据包含两行，每行对应一个正方形，每行包含 4 对整数。每对整数表示正方形的一个顶点的坐标。每行内的坐标按顺时针或逆时针顺序排列。第一行包含边与坐标轴平行的正方形的坐标，第二行包含边与坐标轴成 45 度角的正方形的坐标。所有值均为介于 $-100$ 和 $100$ 之间的整数。"},{"iden":"output","content":"如果正方形相交，请输出 \"_Yes_\"，否则输出 \"_No_\"。你可以以任意大小写形式输出每个字母。"},{"iden":"examples","content":"输入0 0 6 0 6 6 0 61 3 3 5 5 3 3 1输出YES输入0 0 6 0 6 6 0 67 3 9 5 11 3 9 1输出NO输入6 0 6 6 0 6 0 07 4 4 7 7 10 10 7输出YES"},{"iden":"note","content":"在第一个示例中，第二个正方形完全位于第一个正方形内部，因此它们相交。在第二个示例中，两个正方形没有任何公共点。以下是对应示例的图像： "}]}

Let $ S_1 $ be the axis-aligned square defined by its four vertices $ (x_i, y_i) $, $ i = 1, 2, 3, 4 $, given in clockwise or counterclockwise order. Let $ S_2 $ be the 45-degree-rotated square defined by its four vertices $ (u_j, v_j) $, $ j = 1, 2, 3, 4 $, given in clockwise or counterclockwise order. Define: - $ \text{bbox}(S_1) = [\min x_i, \max x_i] \times [\min y_i, \max y_i] $, the axis-aligned bounding box of $ S_1 $ (which equals $ S_1 $ itself). - $ \text{poly}(S_2) $: the convex polygon defined by the four vertices of $ S_2 $. Determine whether $ S_1 \cap S_2 \neq \emptyset $, where intersection includes boundary and interior points. This is equivalent to checking: 1. Whether any vertex of $ S_2 $ lies inside or on the boundary of $ S_1 $, or 2. Whether any vertex of $ S_1 $ lies inside or on the boundary of $ S_2 $, or 3. Whether any edge of $ S_1 $ intersects any edge of $ S_2 $. If any of the above conditions holds, output "Yes"; otherwise, output "No".

Samples

Input #1

0 0 6 0 6 6 0 6
1 3 3 5 5 3 3 1

Output #1

YES

Input #2

0 0 6 0 6 6 0 6
7 3 9 5 11 3 9 1

Output #2

NO

Input #3

6 0 6 6 0 6 0 0
7 4 4 7 7 10 10 7

Output #3

YES

API Response (JSON)

{
  "problem": {
    "name": "A. Two Squares",
    "description": {
      "content": "You are given two squares, one with sides parallel to the coordinate axes, and another one with sides at 45 degrees to the coordinate axes. Find whether the two squares intersect. The interior of the",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF993A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given two squares, one with sides parallel to the coordinate axes, and another one with sides at 45 degrees to the coordinate axes. Find whether the two squares intersect.\n\nThe interior of the...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"给定两个正方形，一个边与坐标轴平行，另一个边与坐标轴成 45 度角。判断这两个正方形是否相交。\\n\\n正方形的内部被视为正方形的一部分，即如果一个正方形完全包含在另一个正方形内，则它们相交。如果两个正方形仅共享一个公共点，也被认为是相交的。\\n\\n输入数据包含两行，每行对应一个正方形，每行包含 4 对整数。每对整数表示正方形的一个顶点...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ S_1 $ be the axis-aligned square defined by its four vertices $ (x_i, y_i) $, $ i = 1, 2, 3, 4 $, given in clockwise or counterclockwise order.\n\nLet $ S_2 $ be the 45-degree-rotated square defin...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments