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

奈芙莲 · 2017-10-09 08:29:56 · 题解

好像只有一篇题解。。那我来再发一篇。。。

判定正方形是否重叠和计算正方形重叠面积楼下都已经说过了。。我就不重复了。

我的思路和楼下不大一样。。

1）对于一个正方形（a, b） 和另一个正方形（c, d），如果 |a - c|+|b - d| > 2 * k 的话，是肯定无解的。（想一想为什么。） 然而这样子还是不是很好处理啊。。。所以我就扩大了一下范围。。。直接把绝对值脱去。。。这样子的话至少不会漏解。。（再想想为什么）。即原来的范围是 |a - c|+|b - d| <= 2*k 可能有解，现在变成了 a + b - c - d <= 2 * k 可能有解。前一种情况是后一种情况的子集。所以可以保证不会漏解。。然后就可以按照横坐标加纵坐标排序。。然后再枚举判定是否合意。。。 还有就是。。重叠个数大于一时及时跳出循环。。可以快很多。。

代码如下：

#include<bits/stdc++.h>
#define read(a) a=getint()
using namespace std;
const int getint() {int x=0, f=1, c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-') f=-1;for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-48;return x*f;}
int n, k, ans, f;
struct node{int x, y;}a[50001];
bool cmp(node a,node b)
{return a.x+a.y<b.x+b.y;}
bool jud(node a,node b){
    return abs(a.x-b.x)<k && abs(a.y-b.y)<k;
}
int main() {
    read(n);read(k);
    for(int i=1;i<=n;++i) read(a[i].x),read(a[i].y);
    sort(a+1,a+n+1,cmp);
    for(int i=1; i<n; ++i) {
        int p = i + 1;
        while(a[i].x+a[i].y  + 2*k >= a[p].x+a[p].y && ans < 2 && p<=n) {
            if(jud(a[i],a[p])) ans ++, f = (k-abs(a[i].x-a[p].x))*(k-abs(a[i].y-a[p].y));
            p++;
        }
        if(ans>1) {puts("-1");return 0;}
    }
    if(ans) printf("%d\n",f);else puts("0");
    return 0;
}