题解 P2202 【[USACO13JAN]方块重叠Square Overlap】

windows250 · 2017-10-09 11:04:21 · 题解

其实可以不用那么复杂的数据结构...

首先我们要知道的是两个正方形A,B出现重叠，当且仅当:

|Xa-Xb|<K && |Ya-Yb|<K

此时重叠部分的面积

S=(K-|Xa-Xb|)*(K-|Ya-Yb|)

得到上述结论后很容易想到两两枚举所有的中心,时间复杂度是O(n^2),而Nmax=50000,显然是会TLE的

因此我们考虑优化:

* 用一个bool变量have记录之前是否已经找到重叠正方形

* 对于第一个中心i:对横坐标从小到大进行排序后再按横坐标从小到大枚举

* 对于第二个中心j:枚举范围为[1,i-1],并且从后往前进行枚举,我们设一个变量temp为点j到点i的距离,那么当temp>=K时就直接跳出对j的枚举过程。如果temp<K 并且满足 |Yi-Yj|<K 且 have=false 就更新ans并标记have , 否则have=true直接输出-1即可。

详细见代码:

#include<bits/stdc++.h>
#define MAXN 50001
#define in(x) x=read()

using namespace std;

typedef long long ll;

inline int read()
{
    int X=0,w=1;
    char ch=getchar();
    while(ch>'9' || ch<'0') {if(ch=='-') w=-1;ch=getchar();}
    while(ch<='9' && ch>='0') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}//读入优化,可忽略 

struct data
{
    ll x,y;
}s[MAXN];//中心坐标 
int N,K;
ll ans=0;
bool have;

inline bool mcomp(const data &a,const data &b)
{
    return a.x<b.x;
}

int main()
{
    in(N);in(K);
    for(int i=1;i<=N;i++)
        in(s[i].x),in(s[i].y);
    sort(s+1,s+N+1,mcomp);
    for(int i=2;i<=N;i++)//按横坐标从小到大枚举中心 
    {
        int tmp=0;
        for(int j=i-1;j>=1;j--)//依次判断第i到i-1,i-2...的距离是否小于k 
        {
            tmp+=(s[j+1].x-s[j].x);
            if(tmp>=K) break;//如果距离大于k继续枚举显然是没有必要的 
            if(abs(s[i].y-s[j].y)<K)
            {
                if(have) {printf("-1\n");return 0;}//之前已经找到过重叠正方形,直接输出-1 
                have=true;ans=(K-tmp)*(K-abs(s[i].y-s[j].y));
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}
//By windows250