方伯伯浇水 - 玉米田品质检测算法与C++代码实现

题目描述

方伯伯有一块玉米田，玉米田可以视为平面直角坐标系上横纵坐标在 -10^5 至 10^5 范围内（包括边界）的一片正方形区域。玉米田内的每个整点（横纵坐标均为整数的点）上都种着一株玉米。

方伯伯连续 m 天对玉米田进行浇水，每天他会选出一个圆心坐标为 (x,y)，半径为 r 的圆形区域，对其中（不包括边界）的每株玉米浇一次水（如果圆形区域超过玉米田边界，超过部分无需浇水）。最开始所有玉米的品质都是 1，每次浇水会让该株玉米的品质增 1。

m 天过后，到了收获的季节，方伯伯想采用抽样检测的方式来调查玉米田的品质。方伯伯给出了 10 株玉米的坐标，他想调查这 10 株玉米品质的平均数。

输入格式

第一行输入一个正整数 m（m≤10^5），代表浇水天数。接下来 m 行，每行输入三个整数 x_i,y_i（-10^5≤x_i,y_i≤10^5）和 r_i（0<r_i≤10^5），代表第 i 天浇水的圆形区域。

接下来 10 行，每行输入两个整数 x_i,y_i（-10^5≤x_i,y_i≤10^5），代表收获季节调查的 10 株玉米的坐标。

输出格式

输出一个数字（保留 2 位小数），代表调查的这 10 株玉米品质的平均数。

样例 #1

样例输入 #1

样例输出 #1

1.40

提示

判断点 (x_1,y_1) 与圆 (x_0,y_0,r_0) 的方法是：

计算点 (x_1,y_1) 到圆心 (x_0,y_0) 的距离的平方 d^2=(x_1-x_0)^2+(y_1-y_0)^2，将这个值与圆的半径的平方 r_0^2 作比较：

如果 d^2<r_0^2，说明点在圆内；
如果 d^2=r_0^2，说明点在圆上；
如果 d^2>r_0^2，说明点在圆外。

C++ 代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 100010;

int n, m;
struct node{
    int x, y, r;
}a[N];
struct node1{
    int x, y;
}b[15];
int f[N];

double dis(int x1, int y1, int x2, int y2){
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int main(){
    scanf("%d", &m);
    for(int i = 1; i <= m; ++ i){
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].r);
        for(int j = max(-100000, a[i].x - a[i].r); j <= min(100000, a[i].x + a[i].r); ++ j){
            int len = sqrt(a[i].r * a[i].r - (j - a[i].x) * (j - a[i].x));
            int l = max(-100000, a[i].y - len);
            int r = min(100000, a[i].y + len);
            f[l] ++;
            f[r + 1] --;
        }
    }
    for(int i = 1; i <= 100000; ++ i) f[i] += f[i - 1];
    double ans = 0;
    for(int i = 1; i <= 10; ++ i){
        scanf("%d%d", &b[i].x, &b[i].y);
        ans += f[b[i].y] * dis(b[i].x, b[i].y, b[i].x, a[1].y);
    }
    printf("%.2lf\n", ans / 10);
    return 0;
}

该代码采用差分数组的方式来记录每株玉米被浇水的次数，然后根据目标玉米的坐标计算其品质，最后输出平均品质。

代码解释：

定义结构体： node 结构体表示浇水的圆形区域，node1 结构体表示目标玉米的坐标。
计算距离： dis 函数用于计算两点之间的距离。
差分数组： f 数组是一个差分数组，用来记录每株玉米被浇水的次数。
循环遍历浇水区域： 循环遍历每一天的浇水区域，使用差分数组记录该区域内所有玉米被浇水的次数。
累加差分数组： 使用前缀和的方法将差分数组转换为前缀和数组，方便查询任意位置的累计值。
计算目标玉米品质： 循环遍历每个目标玉米，根据其坐标和差分数组查询其被浇水的次数，即其品质，然后计算平均品质。

总结：

该代码通过差分数组和前缀和的方式有效地解决了玉米田品质检测的问题，代码简洁易懂，效率较高。

进一步优化：

可以考虑使用二分查找优化判断点是否在圆内的效率。
可以使用 STL 中的 vector 或 map 容器来存储数据，方便代码编写和维护。
可以使用更精确的浮点数类型来提高计算精度。

希望这份解答能够帮助你理解这道题目的思路和实现方法。