牛客假日团队赛43：J Square Overlap

先看题目：https://ac.nowcoder.com/acm/contest/5723/J
题目描述：
给出一些边长都为k的正方形的中心坐标，如果只有一对正方形重叠，则输出重叠面积，如果有多对正方形重叠，输出-1，如果没有正方形重叠，则输出0
解题思路：
画图模拟一下可知，如果两正方形中点坐标为(x1,y1)和(x2,y2)，若|x1-x2| < k && |y1-y2| < k时，才能重叠，其重叠形成的矩形的面积为(k-|y1-y2|)*(k-|x1-x2|)
这道题普通n^2搜索是显然过不了的，但是可以思考思考做出优化。
这道题的n^2搜索

for(int i = 1; i < n; i++) {
    for(int j = i+1; j <= n; j++) {
           判断如果重叠，计算面积...
     }
}

但是我们发现，如果提前对矩形按x坐标排序，矩形i与i-1之间都是相邻关系了，实际上对这两个进行判断是否重叠就行了，如果不重叠就更不可能与之前的重叠了。

虽然也是两次循环，但实际上是O(n)

sort(a+1, a+n+1, cmp);
    for(int i = 2; i <= n; i++) {
        for(int j = i-1; j >= 1; j--) {
            判断如果重叠，计算面积...
        }
    }

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool vis[50100];
struct node{
    int x, y;
}a[50100];
bool cmp(node n, node m)
{
    return n.x < m.x;
}
int main()
{
    int n, k, tot=0;
    ll ans = 0;
    scanf("%d%d",&n,&k);
    for(int i = 1; i <= n; i++) {
        scanf("%d%d",&a[i].x,&a[i].y);
    }
    sort(a+1, a+n+1, cmp);
    for(int i = 2; i <= n; i++) {
        for(int j = i-1; j >= 1; j--) {
            int tmp = a[i].x - a[j].x;
            if(tmp  >= k) break;
            if(abs(a[i].x - a[j].x) < k && abs(a[i].y - a[j].y) < k)
            {
                tot++;
                vis[i] = 1; vis[j] = 1;
                ans += (k-abs(a[i].x - a[j].x))*(k-abs(a[i].y - a[j].y));
                if(tot == 2) {
                    printf("-1\n");
                    return 0;
                }
            }
        }
    }
    printf("%lld\n",ans);
}