方伯伯浇水 - 算法题解与C++代码

方伯伯浇水 - 算法题解与C++代码/n/n题目描述:/n/n方伯伯有一块玉米田，玉米田可以视为平面直角坐标系上横纵坐标在 $-10^5$ 至 $10^5$ 范围内（包括边界）的一片正方形区域。玉米田内的每个整点（横纵坐标均为整数的点）上都种着一株玉米。/n/n方伯伯连续 $m$ 天对玉米田进行浇水，每天他会选出一个圆心坐标为 $(x,y)$，半径为 $r$ 的圆形区域，对其中（不包括边界）的每株玉米浇一次水（如果圆形区域超过玉米田边界，超过部分无需浇水）。最开始所有玉米的品质都是 $1$，每次浇水会让该株玉米的品质增 $1$。/n/n$m$ 天过后，到了收获的季节，方伯伯想采用抽样检测的方式来调查玉米田的品质。方伯伯给出了 $10$ 株玉米的坐标，他想调查这 $10$ 株玉米品质的平均数。/n/n输入格式:/n/n第一行输入一个正整数 $m$（$m/le10^5$），代表浇水天数。/n接下来 $m$ 行，每行输入三个整数 $x_i,y_i$（$-10^5/le x_i,y_i/le 10^5$）和 $r_i$（$0<r_i/le10^5$），代表第 $i$ 天浇水的圆形区域。/n/n接下来 $10$ 行，每行输入两个整数 $x_i,y_i$（$-10^5/le x_i,y_i/le 10^5$），代表收获季节调查的 $10$ 株玉米的坐标。/n/n输出格式:/n/n输出一个数字（保留 $2$ 位小数），代表调查的这 $10$ 株玉米品质的平均数。/n/n样例 #1/n/n样例输入 #1/n/n/n2/n3 4 5/n-1 0 1/n-1 0/n0 0/n1 0/n2 0/n3 0/n-1 -1/n0 -1/n1 -1/n2 -1/n3 -1/n/n/n样例输出 #1/n/n/n1.40/n/n/n提示:/n/n判断点 $(x_1,y_1)$ 与圆 $(x_0,y_0,r_0)$ 的方法是：/n/n计算点 $(x_1,y_1)$ 到圆心 $(x_0,y_0)$ 的距离的平方 $d^2=(x_1-x_0)^2+(y_1-y_0)^2$，将这个值与圆的半径的平方 $r_0^2$ 作比较：/n- 如果 $d^2<r_0^2$，说明点在圆内；/n- 如果 $d^2=r_0^2$，说明点在圆上；/n- 如果 $d^2>r_0^2$，说明点在圆外。/n/nC++代码/n/ncpp/n#include <iostream>/n#include <cstdio>/n#include <cstring>/n#include <cmath>/nusing namespace std;/nconst int N = 100010;/nint n, m, x[N], y[N], r[N], c[N], s[N];/nint main()/n{/n cin >> m;/n for (int i = 1; i <= m; i ++ )/n {/n cin >> x[i] >> y[i] >> r[i];/n for (int j = max(-100000, x[i] - r[i]); j <= min(100000, x[i] + r[i]); j ++ )/n for (int k = max(-100000, y[i] - r[i]); k <= min(100000, y[i] + r[i]); k ++ )/n if ((j - x[i]) * (j - x[i]) + (k - y[i]) * (k - y[i]) <= r[i] * r[i])/n c[(j + 100000) * 200001 + k + 100000] ++ ;/n }/n for (int i = 0; i < 100000 * 2 + 1; i ++ )/n for (int j = 0; j < 100000 * 2 + 1; j ++ )/n s[(i + 1) * 200001 + j + 1] = s[i * 200001 + j + 1] + s[(i + 1) * 200001 + j] - s[i * 200001 + j] + c[i * 200001 + j];/n double ans = 0;/n for (int i = 1; i <= 10; i ++ )/n {/n int a, b;/n cin >> a >> b;/n ans += s[(a + 100000 + 1) * 200001 + b + 100000 + 1] - s[(a + 100000) * 200001 + b + 100000 + 1] - s[(a + 100000 + 1) * 200001 + b + 100000] + s[(a + 100000) * 200001 + b + 100000];/n }/n printf('%.2lf', ans / 10);/n return 0;/n}/n/n/n代码解析:/n/n1. 预处理: 由于坐标范围很大，我们使用哈希表 c 来记录每个点被浇水的次数。 c 的下标由 (x + 100000) * 200001 + y + 100000 计算得到，保证不会发生冲突。/n2. 计算前缀和: 使用二维前缀和 s 来快速求解每个点被浇水的次数。 由于 c 的下标是经过哈希处理的，所以 s 的下标也要相应调整。/n3. 计算平均品质: 对于每个调查点，使用前缀和 s 快速计算该点被浇水的次数，并将其累加到 ans 中。 最后将 ans 除以 $10$，即得到平均品质。/n/n总结: /n/n本题利用二维前缀和技巧，高效地解决了计算每个点被浇水次数的问题，从而快速计算出 $10$ 株玉米的平均品质。/n/n希望这篇文章能够帮助你更好地理解这道算法题，并学习到二维前缀和的应用技巧。