思路
整体
首先，我们可以知道，要满足题意，两个正方形的坐标$(x_i,y_i)(x_j,y_j)$必须满足$\vert x_i-x_j\vert<k$并且$\vert y_i-y_j\vert<k$。如果有且仅有一组正方形满足条件，那么重叠部分的面积$ans=\vert k-(x_i-x_j)\vert\times\vert k-(y_i-y_j)\vert$。
最简单的方法是直接暴力扫描，时间复杂度为$O(n^2)$。
我本来打算写一个二维线段树的，但好像有些大材小用了，难度才提高啊。
根据官方题解，先对所有点排序，然后维护与当前点横坐标差值小于k的所有点的集合，每次查找点集中纵坐标最接近当前点的点，更新答案即可。
如何维护所有满足条件的点呢？因为点是有序的，满足$x_i\le x_{i+1}$，每次只需将无效的点删除即可。
具体实现
使用set维护点集比较方便，删除和插入操作均为log级的。其中set::insert会返回一个pair<iterator,bool>，第一个为插入后的迭代器，第二个为插入是否成功。(参考http://en.cppreference.com/w/cpp/container/set/insert)
cppreference是一个不错的C++参考网站
另外，答案应该用64位整数保存。
代码清单
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<bits/stdc++.h>
using namespace std;
const int N=50005;
typedef pair<int,int> pii;
pii p[N];
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>p[i].first>>p[i].second;
sort(p+1,p+n+1);
set<pii> S;
long long ans=0;
for(int i=1,j=1;i<=n;i++)
{
for(;j<i&&p[i].first-p[j].first>=k;j++)
S.erase(make_pair(p[j].second,j));
set<pii>::iterator it1=S.insert(make_pair(p[i].second,i)).first,it2=it1;
if(it1--!=S.begin()&&p[i].second-it1->first<k)
if(!ans)
ans=(long long)(k-abs(p[i].first-p[it1->second].first))*(k-(p[i].second-it1->first));
else
ans=-1;
if(++it2!=S.end()&&it2->first-p[i].second<k)
if(!ans)
ans=(long long)(k-abs(p[i].first-p[it2->second].first))*(k-(it2->first-p[i].second));
else
ans=-1;
}
cout<<ans<<endl;
return 0;
}
|
时间复杂度为$O(n\log n)$