[NOIP模拟测试10]辣鸡(ljh) 题解

首先计算块内贡献，很显然是$(x_2-x_1)*(y_2-y_1)*2$.

然后考虑矩形之间的贡献，sort一遍分类讨论$n^2$暴力即可。

注意考虑边界情况是否能多两个，以及角对角的情况。

 

另外，排序之后可以通过剪枝排除无用情况(j从i+1开始枚举以及那个break)来实现$n^2$过十万的梦想

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+5;
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;
}
struct block
{
    int x,y,xx,yy;
}s[N];
int cmp2 (block a,block b)
{
    //if(a.x==b.x)return a.xx<b.xx;
    return a.x<b.x;
}
int abss(int val)
{
    return val>=0?val:-val;
}
int n;
ll ans;
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        s[i].x=read(),s[i].y=read(),s[i].xx=read(),s[i].yy=read(),ans+=2LL*(s[i].xx-s[i].x)*(s[i].yy-s[i].y);
//    cout<<ans<<endl;
    sort(s+1,s+n+1,cmp2);
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(s[j].x>s[i].xx+1)break;    
            if(((s[j].xx+1==s[i].x)||(s[j].x-1==s[i].xx))&&((s[j].y-1==s[i].yy)||(s[j].yy+1==s[i].y)))ans++;
            else if(s[j].xx+1==s[i].x||s[j].x-1==s[i].xx)
            {
                if(s[j].yy<=s[i].yy&&s[j].y>=s[i].y)
                {
                    ans+=2LL*(s[j].yy-s[j].y);
                    if(s[i].yy>s[j].yy)ans++;
                    if(s[i].y<s[j].y)ans++;
                }
                else if(s[j].yy>s[i].yy&&s[j].y<s[i].y)
                {
                    ans+=2LL*(s[i].yy-s[i].y)+2;
                }
                else if(s[j].y>=s[i].y&&s[j].y<=s[i].yy)
                {
                    ans+=2LL*(s[i].yy-s[j].y);
                    if(s[j].yy>s[i].yy)ans++;
                    if(s[j].y>s[i].y)ans++;
                }
                else if(s[j].yy>=s[i].y&&s[j].yy<=s[i].yy)
                {
                    ans+=2LL*(s[j].yy-s[i].y);
                    if(s[j].yy<s[i].yy)ans++;
                    if(s[j].y<s[i].y)ans++;
                }
            }
            else if(s[j].y==s[i].yy+1||s[j].yy+1==s[i].y)
            {
                if(s[i].x<=s[j].x&&s[i].xx>=s[j].xx)
                {
                    ans+=2LL*(s[j].xx-s[j].x);
                    if(s[j].x>s[i].x)ans++;
                    if(s[j].xx<s[i].xx)ans++;
                }
                else if(s[i].x>s[j].x&&s[i].xx<s[j].xx)
                {
                    ans+=2LL*(s[i].xx-s[i].x)+2;
                }
                else if(s[j].x>=s[i].x&&s[j].x<=s[i].xx)
                {
                    ans+=2LL*(s[i].xx-s[j].x);
                    if(s[j].x>s[i].x)ans++;
                    if(s[j].xx>s[i].xx)ans++;
                }
                else if(s[j].xx>=s[i].x&&s[j].xx<=s[i].xx)
                {
                    ans+=2LL*(s[j].xx-s[i].x);
                    if(s[j].x<s[i].x)ans++;
                    if(s[j].xx>s[i].xx)ans++;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}