CF958E1.Guard Duty (easy)

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

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.

反抗军舰队担心帝国可能再次发动反击。希迪公主需要判断:能否将 RR 艘反抗军飞船分配去守卫 BB 个基地,使得每个基地恰好拥有一艘守卫飞船,且每艘飞船恰好被分配到一个基地(即该分配构成一个完美匹配)。由于她深知飞行员行事鲁莽,她希望确保任意两条(直线)路径——即从基地到其分配的飞船的连线——在银河平面(即二维平面)上互不相交,从而避免碰撞风险。

输入格式

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.

第一行包含两个用空格分隔的整数 RR 和 BB(1≤R,B≤101 \leq R, B \leq 10)。对于 1≤i≤R1 \leq i \leq R,第 i+1i+1 行包含两个用空格分隔的整数 xix_i 和 yiy_i(∣xi∣,∣yi∣≤10000|x_i|, |y_i| \leq 10000),表示第 ii 艘反抗军飞船的坐标。接下来的 BB 行采用相同格式,表示基地的位置。保证任意两点不重合,且任意三点不共线。

输出格式

If it is possible to connect Rebel spaceships and bases so as satisfy the constraint, output Yes, otherwise output No (without quote).

如果可以连接反抗军的宇宙飞船和基地以满足约束条件,则输出 Yes,否则输出 No(不带引号)。

输入输出样例

  • 输入#1

    3 3
    0 0
    2 0
    3 1
    -2 1
    0 3
    2 2

    输出#1

    Yes
  • 输入#2

    2 1
    1 0
    2 2
    3 1

    输出#2

    No

说明/提示

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.

对于第一个例子,一种可行的方式是按顺序连接反抗军与基地。

对于第二个例子,反抗军与基地之间不存在完美匹配。

输入解题思路,AI测评打分。不知道怎么写?

首页