The trick here is to name the state correctly, then let the implementation follow. For 1453. Maximum Number of Darts Inside of a Circular Dartboard, the solution in this repository is mainly a straightforward implementation solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: straightforward implementation.
The notes already sitting in the source point us in the right direction:
- https://leetcode.com/problems/maximum-number-of-darts-inside-of-a-circular-dartboard/discuss/636332/cpp-O(N3)-solution-with-pictures.
- https://leetcode.com/problems/maximum-number-of-darts-inside-of-a-circular-dartboard/discuss/636345/Simple-Python-O(n3)-Solution-with-picture
- time: O(N^3)
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are getDist, getNumPointsInside, numPoints, getPointsInside.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(N^3)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//https://leetcode.com/problems/maximum-number-of-darts-inside-of-a-circular-dartboard/discuss/636332/cpp-O(N3)-solution-with-pictures.
02//https://leetcode.com/problems/maximum-number-of-darts-inside-of-a-circular-dartboard/discuss/636345/Simple-Python-O(n3)-Solution-with-picture
03//Runtime: 184 ms, faster than 14.29% of C++ online submissions for Maximum Number of Darts Inside of a Circular Dartboard.
04//Memory Usage: 15.5 MB, less than 100.00% of C++ online submissions for Maximum Number of Darts Inside of a Circular Dartboard.
05//time: O(N^3)
06class Solution {
07public:
08 const double eps = 1e-6;
09
10 double getDist(vector<double>& p1, vector<double>& p2){
11 return sqrt(pow(p1[0]-p2[0], 2.0) + pow(p1[1]-p2[1], 2.0));
12 };
13
14 vector<vector<double>> findCircles(vector<double>& p1, vector<double>& p2, int r){
15 vector<vector<double>> centers; //center of circles
16
17 double dist = getDist(p1, p2);
18
19 vector<double> mid = {(p1[0]+p2[0])/2.0, (p1[1]+p2[1])/2.0};
20
21 // cout << "dist: " << dist << endl;
22 // cout << "(" << mid[0] << ", " << mid[1] << ")" << endl;
23
24 //can not find a circle that cover the two points
25 if(dist > 2*r+eps){ //compare with diameter, not radius!
26 //pass
27 }else if(abs(dist-2.0*r) < eps){
28 centers.push_back(mid);
29 }else{
30 double bisection = sqrt(pow(r, 2.0) - pow(dist/2.0, 2.0));
31 //dx and dy should not be taken abs()!!
32 double dx = p1[0]-p2[0];
33 double dy = p1[1]-p2[1];
34
35 /*
36 c1x = mid[0] + bisection*sin(theta)
37 dist*sin(theta) = dy
38 so c1x = mid[0] + bisection*dy/dist
39
40 c1y = mid[1] + bisection*cos(theta)
41 dist*cos(theta) = abs(dx) = -dx
42 so c1y = mid[1] - bisection*dx/dist
43 */
44 //dx and dy could be negative!!
45 double c1x = mid[0] + dy*bisection/dist;
46 double c1y = mid[1] - dx*bisection/dist;
47 centers.push_back({c1x, c1y});
48
49 double c2x = mid[0] - dy*bisection/dist;
50 double c2y = mid[1] + dx*bisection/dist;
51 centers.push_back({c2x, c2y});
52 }
53
54 return centers;
55 };
56
57 int getNumPointsInside(vector<vector<double>>& points, vector<double>& center, int r){
58 int count = 0;
59 for(vector<double>& point : points){
60 if(getDist(point, center) <= r+eps){
61 count++;
62 }
63 }
64 return count;
65 };
66
67 int numPoints(vector<vector<int>>& points, int r) {
68 int n = points.size();
69 vector<vector<double>> centers;
70 int ans = 0;
71
72 vector<vector<double>> dpoints;
73 for (auto&& p : points) dpoints.emplace_back(std::begin(p), std::end(p));
74
75 //iterate through each pair of points
76 for(int i = 0; i < n; i++){
77 for(int j = i+1; j < n; j++){
78 centers = findCircles(dpoints[i], dpoints[j], r);
79 // cout << i << " " << j << ": " << centers.size() << endl;
80 for(int k = 0; k < centers.size(); k++){
81 ans = max(ans, getNumPointsInside(dpoints, centers[k], r));
82 }
83 }
84 }
85
86 //we can always find a circle to include one point
87 //points.size() >= 1
88 return max(ans, 1);
89 }
90};
91
92//angular sweep
93//https://www.geeksforgeeks.org/angular-sweep-maximum-points-can-enclosed-circle-given-radius/
94//Runtime: 52 ms, faster than 89.34% of C++ online submissions for Maximum Number of Darts Inside of a Circular Dartboard.
95//Memory Usage: 16.2 MB, less than 100.00% of C++ online submissions for Maximum Number of Darts Inside of a Circular Dartboard.
96//time: O(N^2logN), space: O(N^2)
97class Solution {
98public:
99 vector<vector<double>> dist;
100
101 double getDist(vector<int>& p1, vector<int>& p2){
102 return sqrt(pow(p1[0]-p2[0], 2.0)+pow(p1[1]-p2[1], 2.0));
103 };
104
105 int getPointsInside(vector<vector<int>>& points, int i, int r){
106 int n = points.size();
107 vector<pair<double, bool>> angles;
108
109 for(int j = 0; j < n; j++){
110 if(j == i || dist[i][j] > 2*r) continue;
111 double B = acos(dist[i][j]/(2.0*r));
112 double A = atan2(points[j][1]-points[i][1],
113 points[j][0]-points[i][0]);
114 double alpha = A-B;
115 double beta = A+B;
116 //reversed definition with geeksforgeeks
117 //because we want alpha(which is entry point) be visited earlier than exit point!
118 angles.emplace_back(alpha, false);
119 angles.emplace_back(beta, true);
120 // cout << j << ", A: " << A << ", B: " << B << " alpha: " << alpha << ", beta: " << beta << endl;
121 }
122
123 // cout << "angles.size() : " << angles.size() << endl;
124
125 sort(angles.begin(), angles.end());
126
127 // for(auto p : angles){
128 // cout << p.first << ", " << p.second << endl;
129 // }
130
131 int count = 1, res = 1;
132
133 for(auto it = angles.begin(); it != angles.end(); it++){
134 if(!it->second){
135 count++;
136 }else{
137 count--;
138 }
139 // cout << "enter: " << (it->second) << ", " << it->first << ", count: " << count << endl;
140 res = max(res, count);
141 }
142
143 // cout << i << ": " << res << endl;
144
145 return res;
146 };
147
148 int numPoints(vector<vector<int>>& points, int r) {
149 int n = points.size();
150 dist = vector<vector<double>>(n, vector<double>(n, 0.0));
151
152 for(int i = 0; i < n-1; i++){
153 for(int j = i+1; j < n; j++){
154 dist[i][j] = dist[j][i] = getDist(points[i], points[j]);
155 // cout << i << ", " << j << " : " << dist[i][j] << endl;
156 }
157 }
158
159 int ans = 0;
160
161 for(int i = 0; i < n; i++){
162 ans = max(ans, getPointsInside(points, i, r));
163 }
164
165 return ans;
166 }
167};Cost
Complexity
Time
O(N^3)
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.