E1. Guard Duty (easy)

Codeforces

IDCF958E1

Time1000ms

Memory256MB

Difficulty—

brute forcegeometrygreedymath

English · Original

Chinese · Translation

Formal · Original

The Rebel fleet is afraid that the Empire might want to strike back again. Princess Heidi needs to know if it is possible to assign _R_ Rebel spaceships to guard _B_ bases so that every base has exactly one guardian and each spaceship has exactly one assigned base (in other words, the assignment is a perfect matching). Since she knows how reckless her pilots are, she wants to be sure that any two (straight) paths – from a base to its assigned spaceship – do not intersect in the galaxy plane (that is, in 2D), and so there is no risk of collision. ## Input The first line contains two space-separated integers _R_, _B_(1 ≤ _R_, _B_ ≤ 10). For 1 ≤ _i_ ≤ _R_, the _i_ + 1\-th line contains two space-separated integers _x__i_ and _y__i_ (|_x__i_|, |_y__i_| ≤ 10000) denoting the coordinates of the _i_\-th Rebel spaceship. The following _B_ lines have the same format, denoting the position of bases. It is guaranteed that no two points coincide and that no three points are on the same line. ## Output If it is possible to connect Rebel spaceships and bases so as satisfy the constraint, output _Yes_, otherwise output _No_ (without quote). [samples] ## Note For the first example, one possible way is to connect the Rebels and bases in order. For the second example, there is no perfect matching between Rebels and bases.

叛军舰队担心帝国可能会再次发动反击。海迪公主需要知道，是否可以将 #cf_span[R] 艘叛军飞船分配给 #cf_span[B] 个基地，使得每个基地恰好有一艘护卫飞船，且每艘飞船恰好被分配到一个基地（即，分配构成一个完美匹配）。由于她知道自己的飞行员多么鲁莽，她希望确保任意两条（直线）路径——从基地到其分配的飞船——在星系平面（即二维平面）上都不相交，从而避免碰撞风险。第一行包含两个用空格分隔的整数 #cf_span[R, B(1 ≤ R, B ≤ 10)]。对于 #cf_span[1 ≤ i ≤ R]，第 #cf_span[i + 1] 行包含两个用空格分隔的整数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[|xi|, |yi| ≤ 10000]），表示第 #cf_span[i] 艘叛军飞船的坐标。接下来的 #cf_span[B] 行格式相同，表示基地的位置。保证任意两点不重合，且任意三点不共线。如果可以将叛军飞船与基地连接以满足约束条件，则输出 _Yes_，否则输出 _No_（不带引号）。对于第一个示例，一种可能的方式是按顺序连接叛军飞船和基地。对于第二个示例，叛军飞船与基地之间不存在完美匹配。 ## Input 第一行包含两个用空格分隔的整数 #cf_span[R, B(1 ≤ R, B ≤ 10)]。对于 #cf_span[1 ≤ i ≤ R]，第 #cf_span[i + 1] 行包含两个用空格分隔的整数 #cf_span[xi] 和 #cf_span[yi]（#cf_span[|xi|, |yi| ≤ 10000]），表示第 #cf_span[i] 艘叛军飞船的坐标。接下来的 #cf_span[B] 行格式相同，表示基地的位置。保证任意两点不重合，且任意三点不共线。 ## Output 如果可以将叛军飞船与基地连接以满足约束条件，则输出 _Yes_，否则输出 _No_（不带引号）。 [samples] ## Note 对于第一个示例，一种可能的方式是按顺序连接叛军飞船和基地。对于第二个示例，叛军飞船与基地之间不存在完美匹配。

**Definitions** Let $ R, B \in \mathbb{Z} $ with $ 1 \leq R, B \leq 10 $ denote the number of Rebel spaceships and bases, respectively. Let $ S = \{s_1, s_2, \dots, s_R\} \subset \mathbb{R}^2 $ be the set of spaceship coordinates. Let $ B = \{b_1, b_2, \dots, b_B\} \subset \mathbb{R}^2 $ be the set of base coordinates. **Constraints** 1. $ R = B $ (perfect matching requires equal numbers). 2. All points in $ S \cup B $ are distinct. 3. No three points in $ S \cup B $ are collinear. **Objective** Determine whether there exists a bijection $ f: S \to B $ such that the set of line segments $ \{ \overline{s_i f(s_i)} \mid s_i \in S \} $ forms a non-crossing perfect matching in $ \mathbb{R}^2 $. Output "Yes" if such a matching exists; otherwise, output "No".

Samples

Input #1

Output #1

Yes

Input #2

Output #2

No

API Response (JSON)

{
  "problem": {
    "name": "E1. Guard Duty (easy)",
    "description": {
      "content": "The Rebel fleet is afraid that the Empire might want to strike back again. Princess Heidi needs to know if it is possible to assign _R_ Rebel spaceships to guard _B_ bases so that every base has exact",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF958E1"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The Rebel fleet is afraid that the Empire might want to strike back again. Princess Heidi needs to know if it is possible to assign _R_ Rebel spaceships to guard _B_ bases so that every base has exact...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "叛军舰队担心帝国可能会再次发动反击。海迪公主需要知道，是否可以将 #cf_span[R] 艘叛军飞船分配给 #cf_span[B] 个基地，使得每个基地恰好有一艘护卫飞船，且每艘飞船恰好被分配到一个基地（即，分配构成一个完美匹配）。由于她知道自己的飞行员多么鲁莽，她希望确保任意两条（直线）路径——从基地到其分配的飞船——在星系平面（即二维平面）上都不相交，从而避免碰撞风险。\n\n第一行包含两个用空格...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ R, B \\in \\mathbb{Z} $ with $ 1 \\leq R, B \\leq 10 $ denote the number of Rebel spaceships and bases, respectively.  \nLet $ S = \\{s_1, s_2, \\dots, s_R\\} \\subset \\mathbb{R}^2 $ be...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments