方伯伯浇水：玉米田品质检测算法与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₁, y₁) 与圆 (x₀, y₀, r₀) 的方法是：

计算点 (x₁, y₁) 到圆心 (x₀, y₀) 的距离的平方 d² = (x₁ - x₀)² + (y₁ - y₀)²，将这个值与圆的半径的平方 r₀² 作比较：

如果 d² < r₀²，说明点在圆内；
如果 d² = r₀²，说明点在圆上；
如果 d² > r₀²，说明点在圆外。

C++代码

#include <cstdio>
#include <cmath>
using namespace std;

const int N = 10010;
int m;
int x[N], y[N], r[N];
int q[N], t;

inline double dist(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", &x[i], &y[i], &r[i]);
    }
    for (int i = 1; i <= 10; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        int cnt = 0;
        for (int j = 1; j <= m; j++) {
            if (dist(a, b, x[j], y[j]) <= r[j]) {
                cnt++;
            }
        }
        q[++t] = cnt;
    }
    double ans = 0;
    for (int i = 1; i <= t; i++) {
        ans += q[i];
    }
    printf("%.2lf", ans / t);
    return 0;
}