AT2644 [ARC076C] Connected?

可以发现这个问题是存在边界的，那么我们可以先放宽一下条件思考一下没有边界的情况。

通过手玩可以发现，若不存在边界总是可以完成这个任务的。

因为两条曲线之间不存在交点，那么每次我们可以从空隙穿过一条直线然后一直绕道另一端。

那么存在边界的情况特殊在一条两个点都在边界上的曲线会将整个矩形划分成两个部分，而此时若两个部分还存在点没有连接就不合法了。

但是，如果这条曲线不全是两个端点都在边界上，那么我们先将其连接对两个端点都在边界上的曲线是不会影响的，一样可以通过缝隙绕道。

那么此时只需要考虑两个端点都在边界上的曲线了。

不难发现，此时合法当且仅当不存在一条曲线将矩形分成两个区域后存在两个端点在不同区域，即不存在两条有端点连成的线段会相交。

因为每条线段都只存在于边界上，可以考虑将二维的矩形变成一维的由边界展开变成的一条线段。

那么此时原图上的线段就会变成新线段上的若干个区间。

可以发现合法的条件当且仅当这些区间只有包含和相离关系。

于是只需要从左往右扫一遍开个栈做一遍括号匹配即可。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for (int i = l; i <= r; ++i)

const int N = 2e5 + 5;

struct node { int x, y, id;} a[N];

int n, m, h, w, x, y, xx, yy, top, st[N], book[N];

bool check(int x, int y) { return (!x || !y || (x == h) || (y == w));}

bool cmp(node a, node b) {

    if(a.y == w) return (b.y < w || b.x > a.x);

    if(a.x == h) return (b.y != w && (b.x < h || b.y < a.y));

    if(!a.y) return (b.y != w && b.x != h && (!b.x || b.x < a.x));

    if(!a.x) return (b.y != w && b.x != h && b.y && b.y > a.y);

}

int main () {

    cin >> h >> w >> m;

    rep(i, 1, m) {

        cin >> x >> y >> xx >> yy;

        if(!check(x, y) || !check(xx, yy)) continue ;

        a[++n] = (node){x, y, i}, a[++n] = (node){xx, yy, i};

    }

    sort(a + 1, a + n + 1, cmp);

    rep(i, 1, n) {

        if(book[a[i].id]) {

            if(a[st[top]].id != a[i].id) { puts("NO"); return 0;}

            else --top;

        }

        else st[++top] = i, book[a[i].id] = 1;

    }

    puts("YES");

    return 0;

}

可以发现，先放宽条件是一个当条件非常多的时候对一道题下手的一个良好方法。

其次，当某些平面 / 三维空间上只涉及边界时，可以考虑降维将边界拆成一条连续的线段然后在序列上完成这个问题。

巴特西

AT2644 [ARC076C] Connected?

最新文章

热门文章