Rt,思路是按横坐标排序,然后对于每个点暴力往后找,找到横坐标太大了就换下一个点接着找。
这样可以卡成 O(n2),于是 T 了一个点,然后在代码里加了一个,如果运行次数超过 2e7 直接输出并结束,就过了。
#include<bits/stdc++.h>
#define N 50005
using namespace std;
int n,k;
struct node
{
int x,y;
}a[N];
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",&a[i].x,&a[i].y);
sort(a+1,a+1+n,cmp);
long long ans = 0;int tot = 0;
for(int i = 1;i < n;i++)
for(int j = i+1;j <= n;j++)
{
if(a[i].x + k <= a[j].x || tot > 2e7)break;
if(abs(a[i].y-a[j].y) < k)
{
if(ans)return printf("-1"),0;
long long s = (k-(a[j].x-a[i].x))*(k-abs(a[j].y-a[i].y));
ans = s;
}
tot++;
}
printf("%lld\n",ans);
return 0;
}