题目简介：
给你一个数组 towers 和一个整数 radius 。
数组 towers 中包含一些网络信号塔，其中 towers[i] = [xi, yi, qi]表示第 i 个网络信号塔的坐标是 (xi, yi) 且信号强度参数为 qi 。所有坐标都是在 X-Y 坐标系内的 整数 坐标。两个坐标之间的距离用 欧几里得距离 计算。
整数 radius 表示一个塔 能到达 的 最远距离 。如果一个坐标跟塔的距离在 radius 以内，那么该塔的信号可以到达该坐标。在这个范围以外信号会很微弱，所以 radius 以外的距离该塔是 不能到达的 。
如果第 i 个塔能到达 (x, y) ，那么该塔在此处的信号为 ⌊qi / (1 + d)⌋ ，其中 d 是塔跟此坐标的距离。一个坐标的 信号强度 是所有 能到达 该坐标的塔的信号强度之和。
请你返回数组 [cx, cy] ，表示 信号强度 最大的 整数 坐标点 (cx, cy) 。如果有多个坐标网络信号一样大，请你返回字典序最小的 非负 坐标。
注意：
- 坐标
(x1, y1) 字典序比另一个坐标 (x2, y2) 小，需满足以下条件之一：
- 要么
x1 < x2 ，
- 要么
x1 == x2 且 y1 < y2 。
⌊val⌋ 表示小于等于 val 的最大整数（向下取整函数）。
示例 1：
1
2
3
4
5
6
7
8
| 输入：towers = [[1,2,5],[2,1,7],[3,1,9]], radius = 2
输出：[2,1]
解释：
坐标 (2, 1) 信号强度之和为 13
- 塔 (2, 1) 强度参数为 7 ，在该点强度为 ⌊7 / (1 + sqrt(0)⌋ = ⌊7⌋ = 7
- 塔 (1, 2) 强度参数为 5 ，在该点强度为 ⌊5 / (1 + sqrt(2)⌋ = ⌊2.07⌋ = 2
- 塔 (3, 1) 强度参数为 9 ，在该点强度为 ⌊9 / (1 + sqrt(1)⌋ = ⌊4.5⌋ = 4
没有别的坐标有更大的信号强度。
|
提示：
1 <= towers.length <= 50towers[i].length == 30 <= xi, yi, qi <= 501 <= radius <= 50
思路：
首先遍历所有信号塔，获得最大的x和最大的y，我们所要遍历的坐标就在0 <= i <= x, 0 <= j <= y内。（因为距离越大，信号越弱，且坐标为非负）
然后只要依次遍历坐标，暴力枚举即可。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| class Solution {
public:
vector<int> bestCoordinate(vector<vector<int>>& towers, int radius) {
int max_x = -1;
int max_y = -1;
int max_sign = -1;
int res_x, res_y;
for(int i = 0; i < towers.size(); i++){
if(towers[i][0] > max_x)
max_x = towers[i][0];
if(towers[i][1] > max_y)
max_y = towers[i][1];
}
for(int i = 0; i <= max_x; i++){
for(int j = 0; j <= max_y; j++){
int now_sign = 0;
for(int k = 0; k < towers.size(); k++){
double dis = sqrt(pow(towers[k][0] - i, 2) +
pow(towers[k][1] - j, 2));
if(dis <= radius){
now_sign += floor(towers[k][2] / (1 + dis));
}
}
if(now_sign > max_sign){
max_sign = now_sign;
res_x = i;
res_y = j;
}
}
}
return {res_x, res_y};
}
};
|
