玄学优化过了,请求加强数据
查看原帖
玄学优化过了,请求加强数据
1037502
luxiaomao楼主2024/11/11 21:36

Rt,思路是按横坐标排序,然后对于每个点暴力往后找,找到横坐标太大了就换下一个点接着找。

这样可以卡成 O(n2)O(n^2),于是 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;
}
2024/11/11 21:36
加载中...