题解：SP702 EXPAND - Barn Expansion

· · 题解

SP702 EXPAND - Barn Expansion 牛棚扩张

【双倍经验】

解题思路

一种基于“贪心-区间问题”的优雅暴力解题方法。

根据题意，如果两个牛棚的边有相交的部分，那么这两个牛棚都不可扩张。

首先观察样例，我们可以得出下图：

此时结合题面，有人就会得出结论：两两矩形之间不可能相交。

说的太对了！但这条信息对于本篇题解没有任何意义。

请再次用我们大大的眼睛去好好盯一盯这张图片，将眼光从最左边，缓缓地移到最右边——你就会发现，如果两个矩形的边有重合的部分，那两个矩形在横坐标轴上的投影必然相交——假设共用一个端点也算相交的话。（不用我解释投影是什么吧）

这也太明显了！小学二年级的同学也可以看出来好吧。这真的对解题有帮助吗？

你想想，如果这样的话，那我是不是可以利用这一条性质，写一份优化过的 O(n^2) 的暴力……嗯？

按照左边界为第一关键字，下边界为第二关键字（用于加速），对所有矩形进行排序。然后，从左往右，选定一个矩形，再从左往右扫描与他横坐标相交的矩形，判断纵坐标上是否相交，是的话就将两者全部标记（说白了就是暴力）。

虽然时间复杂度为 O(n^2)，但实际可以跑得飞快。

关键代码如下：

sort(p+1,p+1+n,cmp);
for(int i=1;i<=n;i++)
{
    int l=p[i].a,r=p[i].c,u=p[i].d,d=p[i].b;  //左、右、上、下
    for(int j=i+1;j<=n&&p[j].a<=r;j++)
    {
        if(p[j].d>=d&&p[j].b<=u)could[i]=could[j]=false;
    }
}

实现细节

本题除了要多测清空外没有任何细节。

完整代码

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
struct Square{
    int a,b,c,d;
}p[50005];
inline bool cmp(Square A,Square B)
{
    return A.a==B.a?A.b<B.b:A.a<B.a;
}
bool could[50005];
int T,n,ans;
int main()
{ 
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d %d %d %d",&p[i].a,&p[i].b,&p[i].c,&p[i].d);
            if(p[i].a>p[i].c)swap(p[i].a,p[i].c);
            if(p[i].b>p[i].d)swap(p[i].b,p[i].d);
            could[i]=true;
        }
        sort(p+1,p+1+n,cmp);
        for(int i=1;i<=n;i++)
        {
            int l=p[i].a,r=p[i].c,u=p[i].d,d=p[i].b;  //左、右、上、下
            for(int j=i+1;j<=n&&p[j].a<=r;j++)
            {
                if(p[j].d>=d&&p[j].b<=u)could[i]=could[j]=false;
            }
        }
        ans=0;
        for(int i=1;i<=n;i++)if(could[i])ans++;
        printf("%d\n",ans);
    }
    return 0;
}