题解 P4261 【[Code+#3]白金元首与克劳德斯】

· · 题解

考验大家初中物理的时候到了~

本题题解

首先我们发现所有的云只有两种运动方向，水平向右和竖直向上

那么我们可以变化一下参考系，我们以一个竖直向上1单位速度每秒运动的点作为参考系

那么我们会发现此时所有水平运动的云都是不动的了

现在所有水平向右运动的云全部是沿着斜下方45度的方向运动了

又因为在0时刻所有云互不相交，因此所有水平运动的云互不相交，并且所有竖直的云也是互不相交的，所以同一个点最多被两朵云覆盖，而且一个是水平运动的另一个是竖直运动的云，所以答案要么是1要么是2对应着是否出现过云相交的情况

那么问题就非常简单了，我们的问题现在变成了一堆不动云和一堆45度运动的云会不会相交的问题，这个问题还是相当好解决的，我们先将整个坐标系旋转45度,现在的问题变成了一堆水平运动的斜矩形和一堆不动的斜矩形会不会相交的问题了

然后我们发现由于运动的时间是无限长，因此其实问题就判断一堆线段会不会相交的问题……具体点就是你发现每一个斜着的矩形可以抽象成一个上端点是顶点中y坐标最大值，下端点是顶点y坐标中的最小值的线段

然后我比较傻……，我是把所有的坐标全部离散化之后，将所有竖直云对应的线段全部区间+1然后对于每一个水平的云对应的线段,查一下区间和判一下是不是全是0来进行判断的…………

上代码~

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<map> 
using namespace std;const int N=1e5+10;typedef long long ll; 
int n;int x[N];int y[N];int w[N];int h[N];int t[N];int sum[4*N];
map <int,int> mp;int T;
inline void solve()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d%d%d%d",&x[i],&y[i],&w[i],&h[i],&t[i]);
    for(int i=1;i<=n;i++){mp[x[i]+y[i]+1]=1,mp[x[i]+y[i]+w[i]+h[i]]=1;}
    map <int,int> :: iterator it,it1;//大力离散化
    for(it=mp.begin(),it1=it,++it1;it1!=mp.end();++it,++it1)it1->second+=it->second;
    for(int i=1;i<=n;i++)
    {
        if(t[i]==0)//然后区间加
        {
            int l=mp[x[i]+y[i]+1];int r=mp[x[i]+y[i]+w[i]+h[i]];
            for(int j=l;j<=r;j++)sum[j]=1;
        }
    }for(int i=1;i<=(int)mp.size();i++)sum[i]+=sum[i-1];
    for(int i=1;i<=n;i++)//区间求和
    {
        if(t[i]==1)
        {
            int l=mp[x[i]+y[i]+1];int r=mp[x[i]+y[i]+w[i]+h[i]];
            if(sum[l]!=sum[r]){printf("2\n");return;}
        }
    }printf("1\n");
}
inline void clear()
{for(int i=1;i<=(int)mp.size();i++)sum[i]=0;mp.clear();}
int main()//拜拜程序~
{scanf("%d",&T);for(int z=1;z<=T;z++)solve(),clear();return 0;}