CF958E1 Guard Duty (easy) 题解
题面传送门(luogu) | 题面传送门(CF)
本题的翻译好像少了点东西(建议直接阅读英文题面,推荐一个好点的翻译),这里进行补充:
- 题面翻译:在一个二维平面中,有 \(R\) 艘飞船和 \(B\) 个基地,给出他们的坐标,判断是否存在一种方案,使用一些不相交线段连接飞船和基地,使得任意一艘飞船有且仅有一个基地与之相连,任意一个基地有且仅有一艘飞船与之相连,且任意一艘飞船和基地都只在一条线段的端点上。
- 输入格式:
It is guaranteed that no two points coincide and that no three points are on the same line.
-> 保证没有两个点重合,也没有三个点在同一条线段上。
阅读英文题面后,我们易知如下:
- 当 \(R\not =B\) 时(eg:样例二),不满足"任意一艘飞船有且仅有一个基地与之相连,任意一个基地有且仅有一艘飞船与之相连"的条件,故无解,输出
No
。 - 当 \(R=B\) 时(eg:样例一),考虑分别对每艘飞船、基地的坐标进行排序,则连接第 \(i\) 艘飞船与第 \(i\) 个基地后,一定有连接而得到的 \(R\) 条线段不相交(因为输入格式中保证没有两个点重合,也没有三个点在同一条线段上)。故一定有解,输出
Yes
。
代码(禁止抄袭、复制题解)