题解 P7014 [CERC2013]Chain & Co.

Graphcity · 2023-04-20 21:48:19 · 题解

首先注意到同一维相等的矩形都是不能扣起来的，所以只用考虑 x,y,z 相等的三类矩形的划分方式。

考虑 y 相等的矩形 A 和 z 相等的矩形 B 扣起来的条件：

这两个条件都很好判断。关键在于 x 坐标。分析这些矩形在 x 轴上的投影，可以发现投影都是一个区间，而且有 A 中矩形的投影区间与 B 中矩形的投影区间相交。

正难则反，扫描线判断有无两个区间相离或者包含即可。

其它情况类似，只需将坐标变换一下。时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=1e6,inf=1e9+7;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

int T,n;
struct Square{int x1,y1,z1,x2,y2,z2;};
struct Node{int l,r,op;};
inline bool operator<(Node a,Node b) {return a.l<b.l;}
vector<Square> X,Y,Z;

vector<Node> v;
inline int CheckYZ()
{
    if(Y.empty() || Z.empty()) return 0;
    int Zmn=inf,Zmx=-inf,Ymn=inf,Ymx=-inf;
    for(auto i:Z) Zmn=min(Zmn,i.z1),Zmx=max(Zmx,i.z2);
    for(auto i:Y) Ymn=min(Ymn,i.y1),Ymx=max(Ymx,i.y2);
    for(auto i:Y) if(i.z1>=Zmn || i.z2<=Zmx) return 0;
    for(auto i:Z) if(i.y1>=Ymn || i.y2<=Ymx) return 0;
    int yl=-inf,yr=inf,zl=-inf,zr=inf;
    v.clear(),v.shrink_to_fit();
    for(auto i:Y)
        yl=max(yl,i.x1),yr=min(yr,i.x2),
        v.push_back((Node){i.x1,i.x2,1});
    for(auto i:Z) 
        zl=max(zl,i.x1),zr=min(zr,i.x2),
        v.push_back((Node){i.x1,i.x2,2});
    if(yr<=zl || zr<=yl) return 0;
    sort(v.begin(),v.end()),yr=zr=-inf;
    for(auto i:v)
    {
        if(i.op==1) {if(zr>=i.r) return 0; yr=max(yr,i.r);}
        if(i.op==2) {if(yr>=i.r) return 0; zr=max(zr,i.r);}
    }
    return 1;
}
inline int CheckXY()
{
    if(X.empty() || Y.empty()) return 0;
    swap(X,Z);
    for(auto &i:X) swap(i.x1,i.z1),swap(i.x2,i.z2);
    for(auto &i:Y) swap(i.x1,i.z1),swap(i.x2,i.z2);
    for(auto &i:Z) swap(i.x1,i.z1),swap(i.x2,i.z2);
    int chk=CheckYZ();
    swap(X,Z);
    for(auto &i:X) swap(i.x1,i.z1),swap(i.x2,i.z2);
    for(auto &i:Y) swap(i.x1,i.z1),swap(i.x2,i.z2);
    for(auto &i:Z) swap(i.x1,i.z1),swap(i.x2,i.z2);
    return chk;
}
inline int CheckXZ()
{
    if(X.empty() || Z.empty()) return 0;
    swap(X,Y);
    for(auto &i:X) swap(i.x1,i.y1),swap(i.x2,i.y2);
    for(auto &i:Y) swap(i.x1,i.y1),swap(i.x2,i.y2);
    for(auto &i:Z) swap(i.x1,i.y1),swap(i.x2,i.y2);
    int chk=CheckYZ();
    swap(X,Y);
    for(auto &i:X) swap(i.x1,i.y1),swap(i.x2,i.y2);
    for(auto &i:Y) swap(i.x1,i.y1),swap(i.x2,i.y2);
    for(auto &i:Z) swap(i.x1,i.y1),swap(i.x2,i.y2);
    return chk;
}

inline void Solve()
{
    n=read(),X.clear(),Y.clear(),Z.clear();
    X.shrink_to_fit(),Y.shrink_to_fit(),Z.shrink_to_fit();
    For(i,1,n)
    {
        int x1=read(),y1=read(),z1=read(),x2=read(),y2=read(),z2=read();
        if(x1>x2) swap(x1,x2); if(y1>y2) swap(y1,y2); if(z1>z2) swap(z1,z2);
        Square k=(Square){x1,y1,z1,x2,y2,z2};
        if(x1==x2) X.push_back(k);
        if(y1==y2) Y.push_back(k);
        if(z1==z2) Z.push_back(k);
    }
    if(n==1) {printf("NO\n"); return;}
    if((!X.empty())+(!Y.empty())+(!Z.empty())==1) {printf("NO\n"); return;}
    int XY=CheckXY(),XZ=CheckXZ(),YZ=CheckYZ();
    if((!X.empty())+(!Y.empty())+(!Z.empty())==2)
    {
        if(XY || YZ || XZ) printf("YES\n");
        else printf("NO\n");
        return;
    }
    if((XY && XZ) || (XY && YZ) || (XZ && YZ)) printf("YES\n");
    else printf("NO\n");
}

int main()
{
    T=read();
    while(T--) Solve();
    return 0;
}