leetcode 第189周周赛 圆形靶内的最大飞镖数量

本文主要是介绍leetcode 第189周周赛 圆形靶内的最大飞镖数量，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解题思路：Angular Sweep
代码如下：

import math
class Solution:def numPoints(self, points: List[List[int]], r: int) -> int:size = len(points)if size == 0:return 0#vec[i][j]表示points[i]指向points[j]的向量vec = [[[0, 0] for j in range(size)] for i in range(size)]for i in range(size):for j in range(i+1, size):jx, jy = points[j][0], points[j][1]ix, iy = points[i][0], points[i][1]vec[i][j] = [jx-ix, jy-iy]vec[j][i] = [ix-jx, iy-jy]def helper(i):angular = []for j in range(size):if i != j and (dist:= sum([x**2 for x in vec[i][j]])) <= 4*r*r:C = math.acos(math.sqrt(dist) / (2 * r))T = math.atan2(vec[i][j][1], vec[i][j][0])theta1 = T - C #进入圆theta2 = T + C #离开圆angular.append([theta1, 1])angular.append([theta2, 0])res = cnt = 1angular.sort(key=lambda x:[x[0], -x[1]])for a in angular:if a[1]:cnt += 1else:cnt -=1res = max(res, cnt)return resans = 0for i in range(size):ans = max(ans, helper(i))return ans

这篇关于leetcode 第189周周赛 圆形靶内的最大飞镖数量的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---