题解 CF958E1 Guard Duty (easy)

这是一道诈骗题

简要题意

给你 $n$ 个 $R$ 点和 $m$ 个 $B$ 点，现在给你这些点的坐标，问能否在这两类点间连线来构造出一种情况使得一个线段两边分别是 $R$ 和 $B$。

策略分析

不合法情况

当 $n\ne m$ 时，我们顺次连接 $R$ 和 $B$，先不考虑相交不相交，发现连到最后要么 $R$ 和 $R$ 相连，要么 $B$ 和 $B$ 相连，一定不合法。

合法情况

当 $n=m$ 时，答案一定合法

正确性证明

我们设有点 $R_1,R_2,B_1,B_2$，那么我们加上边 $(R_1,B_1),(R_2,B_1),(R_1,B_2)$，发现相交了，如下图：

但我们发现，当这种相交情况出现时，我们只需要改连边 $(R_1,B_1),(R_2,B_1),(R_2,B_2)$，就一定能变成不相交的情况，如下图：

于是我们做完了，下面是AC代码

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <cstdio>
using namespace std;

namespace SHAWN {
    int n, m;
    int work()
    {   
        cin >> n >> m;
        n == m ? cout << "Yes\n" : cout << "No\n";
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}

说些什么吧！

twikoo