C++ 算法题：方伯伯浇水 2 - 优化玉米品质，平均数计算 - 常规

方伯伯浇水 2 - 优化玉米品质，平均数计算

题目描述

方伯伯有一块玉米田，玉米田可以视为平面直角坐标系上横纵坐标在 -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 <iomanip>
#include <cmath>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int n;

struct Point
{
    int x, y;
} p[N], q[10];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        int x, y, r;
        cin >> x >> y >> r;
        for (int j = max(-100000, x - r); j <= min(100000, x + r); j ++ )
            for (int k = max(-100000, y - r); k <= min(100000, y + r); k ++ )
                if ((j - x) * (j - x) + (k - y) * (k - y) <= r * r)
                    p[(j + 100000) * 200001 + k + 100000] ++ ;
    }

    for (int i = 0; i < 10; i ++ )
        cin >> q[i].x >> q[i].y;

    double res = 0;
    for (int i = 0; i < 10; i ++ )
        res += p[(q[i].x + 100000) * 200001 + q[i].y + 100000];
    res /= 10;

    cout << fixed << setprecision(2) << res << endl;

    return 0;
}

代码解析

首先定义一个二维数组 p，用于记录每个点的品质，由于坐标范围为 -10^5 到 10^5，因此使用一个一维数组来存储所有点的信息，大小为 200001 * 200001（即 2 * 10^5 + 1）。
循环遍历每个浇水圆形区域，计算圆形区域内的所有点，并将这些点的品质加 1。
最后循环遍历 10 个调查的点的坐标，从数组 p 中获取其品质，并计算平均值。

总结

这道题的重点在于如何高效地计算圆形区域内的所有点，并记录每个点的品质。使用一个一维数组来存储所有点的信息，可以有效地利用空间，提高代码效率。