You have a very large square wall and a circular dartboard placed on the wall. You have been challenged to throw darts into the board blindfolded. Darts thrown at the wall are represented as an array of points on a 2D plane.
Return the maximum number of points that are within or lie on any circular dartboard of radius r.
Example 1:
Input: points = [[-2,0],[2,0],[0,2],[0,-2]], r = 2 Output: 4 Explanation: Circle dartboard with center in (0,0) and radius = 2 contain all points.
Example 2:
Input: points = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5 Output: 5 Explanation: Circle dartboard with center in (0,4) and radius = 5 contain all points except the point (7,8).
Example 3:
Input: points = [[-2,0],[2,0],[0,2],[0,-2]], r = 1 Output: 1
Example 4:
Input: points = [[1,2],[3,5],[1,-1],[2,3],[4,1],[1,3]], r = 2 Output: 4
Constraints:
1 <= points.length <= 100points[i].length == 2-10^4 <= points[i][0], points[i][1] <= 10^41 <= r <= 5000
Solution 1: Angular Sweep
See for more details: https://www.geeksforgeeks.org/angular-sweep-maximum-points-can-enclosed-circle-given-radius/
Time complexity: O(n^2*logn)
Space complexity: O(n^2)
C++
|
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 47 48 49 50 51 52 53 |
// Author: Huahua // Python-Like enumerate() In C++17 // http://reedbeta.com/blog/python-like-enumerate-in-cpp17/ template <typename T, typename TIter = decltype(std::begin(std::declval<T>())), typename = decltype(std::end(std::declval<T>()))> constexpr auto enumerate(T && iterable) { struct iterator { size_t i; TIter iter; bool operator != (const iterator & other) const { return iter != other.iter; } void operator ++ () { ++i; ++iter; } auto operator * () const { return std::tie(i, *iter); } }; struct iterable_wrapper { T iterable; auto begin() { return iterator{ 0, std::begin(iterable) }; } auto end() { return iterator{ 0, std::end(iterable) }; } }; return iterable_wrapper{ std::forward<T>(iterable) }; } class Solution { public: int numPoints(vector<vector<int>>& points, int r) { const int n = points.size(); vector<vector<double>> d(n, vector<double>(n)); for (const auto& [i, pi] : enumerate(points)) for (const auto& [j, pj] : enumerate(points)) d[i][j] = d[j][i] = sqrt((pi[0] - pj[0]) * (pi[0] - pj[0]) + (pi[1] - pj[1]) * (pi[1] - pj[1])); int ans = 1; for (const auto& [i, pi] : enumerate(points)) { vector<pair<double, int>> angles; // {angle, event_type} for (const auto& [j, pj] : enumerate(points)) { if (i != j && d[i][j] <= 2 * r) { const double a = atan2(pj[1] - pi[1], pj[0] - pi[0]); const double b = acos(d[i][j] / (2 * r)); angles.emplace_back(a - b, -1); // entering angles.emplace_back(a + b, 1); // exiting } } // If angles are the same, entering points go first. sort(begin(angles), end(angles)); int pts = 1; for (const auto& [_, event] : angles) ans = max(ans, pts -= event); } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment