题解 P2202 【[USACO13JAN]Square Overlap S】

45dino · 2020-07-11 16:51:09 · 题解

蓝题吗？可能不那么难。

首先可以想到对于点 i 和 l ，如果 abs(l_x-i_x)<k 并且 abs(l_y-i_y)<k ，这两个矩形就会有重叠，重叠面积为 abs(k-abs(i_x-l_x))\times abs(k-abs(i_y-l_y)) 。

对于其他情况，计算重叠的次数特判即可。

此时复杂度为 O(n^2) ，不才怪。

考虑利用单调性，按 x 值排序，对于点 i ，枚举点 l ，此时复杂度为 O(nlog_2n) 。

喜闻乐见的代码：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y;
} pos[50001];
int n,k,num,ans;
bool cmp(node x,node y)
{
    return x.x<=y.x;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&pos[i].x,&pos[i].y);
    sort(pos+1,pos+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        int l=i+1;
        while(l<=n&&abs(pos[l].x-pos[i].x)<k)
        {
            if(abs(pos[l].y-pos[i].y)<k)
            {
                num++;
                if(num==2)
                {
                    puts("-1");
                    return 0;
                }
                ans=abs(k-abs(pos[i].x-pos[l].x))*abs(k-abs(pos[i].y-pos[l].y));
            }
            l++;
        }
    }
    if(num)
        cout<<ans;
    if(num==0)
        puts("0");
    return 0;
}