题解

思路概述

• 坐标范围仅在 0…128，最多 129×129 个候选发射点。直接枚举所有交叉口 (i,j)，用绝对值判断是否落在以该点为中心、边长 2d 的正方形内，即 |x-i|≤d && |y-j|≤d。
• 对每个候选位置累计当前覆盖到的公共场所数量，与当前最优值比较并记录等于最优值的方案数。

复杂度

枚举范围固定，最坏遍历 129×129×n 次，显然可以接受。空间只有常量。

#include<cstdio>
#include<cstring>
using namespace std;
int d,n,x[30],y[30],k[30],ans1,ans2,zz,i,j,l; 
main()
{
	scanf("%d%d",&d,&n);
	for(i=1;i<=n;i++)
	scanf("%d%d%d",&x[i],&y[i],&k[i]);
	for(i=0;i<=128;i++)
	for(j=0;j<=128;j++)
	{
		zz=0;
		for(l=1;l<=n;l++)
		if(i-x[l]<=d&&x[l]-i<=d&&j-y[l]<=d&&y[l]-j<=d)
		zz=zz+k[l];
		if(zz==ans2)
		ans1++;
		else if(zz>ans2)
		{
			ans1=1;
			ans2=zz;
		}
	}
	printf("%d %d",ans1,ans2);
}