方伯伯浇水2 - C++ 代码详解 | 玉米田浇水问题 - 常规

方伯伯浇水2 - 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 <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 100010;

int n, m;
int q[N], hh, tt;
int h[N], e[N], ne[N], idx;
int d[N]; // 存储点到第一天圆心的距离
int cnt[N]; // 存储每个点被浇水的次数
int sum[N]; // 存储每个点的品质
int x[N], y[N], r[N]; // 存储每天圆心的坐标和半径
int X[N], Y[N]; // 存储每个点的坐标

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int get(int x, int y)
{
    return (x + 100000) * 200001 + (y + 100000);
}

void bfs(int sx, int sy)
{
    memset(d, -1, sizeof d);
    d[get(sx, sy)] = 0;
    q[0] = get(sx, sy);
    hh = 0, tt = 1;
    while (hh != tt)
    {
        int t = q[hh ++ ];
        int x = t / 200001 - 100000, y = t % 200001 - 100000;
        for (int i = -1; i <= 1; i ++ )
            for (int j = -1; j <= 1; j ++ )
            {
                int a = x + i, b = y + j;
                if (a < -100000 || a > 100000 || b < -100000 || b > 100000) continue;
                int u = get(a, b);
                if (d[u] != -1) continue;
                d[u] = d[t] + 1;
                q[tt ++ ] = u;
            }
    }
}

int main()
{
    scanf("%d", &m);
    for (int i = 0; i < m; i ++ )
    {
        scanf("%d%d%d", &x[i], &y[i], &r[i]);
        bfs(x[i], y[i]);
        for (int j = 0; j < 10; j ++ )
        {
            int a = X[j], b = Y[j];
            int t = get(a, b);
            if (d[t] != -1 && d[t] < r[i]) // 如果点在圆内
            {
                add(i, j); // 在第 i 天浇水的圆内的点 j
                cnt[j] ++ ;
            }
        }
    }

    for (int i = 0; i < 10; i ++ ) scanf("%d%d", &X[i], &Y[i]);

    for (int i = 0; i < m; i ++ )
    {
        for (int j = h[i]; ~j; j = ne[j])
        {
            int k = e[j];
            sum[k] += i + 1;
        }
    }

    double res = 0;
    for (int i = 0; i < 10; i ++ ) res += (double)sum[i] / cnt[i];
    printf("%.2lf\n", res / 10);

    return 0;
}

代码解析

数据结构:

使用数组 x, y, r 存储每天圆心的坐标和半径。
使用数组 X, Y 存储需要调查的 10 株玉米的坐标。
使用邻接表 h, e, ne 记录每个圆形区域内的玉米编号，方便统计每个玉米被浇水的次数。
使用数组 d 存储每个点到当天圆心的距离。
使用数组 cnt 存储每个点被浇水的次数。
使用数组 sum 存储每个点的品质。

BFS 算法:

函数 bfs(sx, sy) 使用广度优先搜索算法 (BFS) 计算每个点到圆心的距离，并判断该点是否在圆形区域内。
使用队列 q 存储需要访问的点。
使用 d 数组记录每个点到圆心的距离。

计算品质:

使用 add(i, j) 函数将第 i 天浇水的圆形区域内的玉米编号 j 加入到邻接表中。
使用循环遍历邻接表，统计每个点被浇水的次数 cnt[j]。
计算每个点的品质 sum[j]，每个点被浇水一次，品质增加 1。
最后计算 10 株玉米品质的平均数。

总结

本题使用了 BFS 算法、图的存储等技巧，代码结构清晰易懂。通过学习本题的代码，可以加深对图论算法和 C++ 代码实现的理解。