玉米田浇水问题 - 计算玉米品质平均数

题目描述

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

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

2
3 4 5
-1 0 1
-1 0
0 0
1 0
2 0
3 0
-1 -1
0 -1
1 -1
2 -1
3 -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$，说明点在圆外。

算法1

(暴力枚举) $O(mn)$

blablabla

时间复杂度

参考文献

C++ 代码

// 暴力枚举
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int m, x, y, r, sum = 0;
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> x >> y >> r;
        for (int j = 0; j < 10; j++) {
            cin >> x >> y;
            if (pow(x, 2) + pow(y, 2) < pow(r, 2)) {
                sum++;
            }
        }
    }
    cout << fixed << setprecision(2) << (double)sum / 10 << endl;
    return 0;
}

算法2

(暴力枚举) $O(mn)$

blablabla

时间复杂度

参考文献

C++ 代码

// 暴力枚举
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int m, x, y, r, sum = 0;
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> x >> y >> r;
        for (int j = 0; j < 10; j++) {
            cin >> x >> y;
            if (pow(x, 2) + pow(y, 2) < pow(r, 2)) {
                sum++;
            }
        }
    }
    cout << fixed << setprecision(2) << (double)sum / 10 << endl;
    return 0;
}