当前位置：首页 > news >正文

【几何】个人练习-Leetcode-1453. Maximum Number of Darts Inside of a Circular Dartboard

news 2025/7/4 9:15:51

题目链接：https://leetcode.cn/problems/maximum-number-of-darts-inside-of-a-circular-dartboard/description/

题目大意：给出一系列点和一个圆的半径，（寻找一个圆心）求这个半径的圆最多能覆盖多少个点。

思路：几何上，如果一个圆能够覆盖N个点，那么在这N个点中，一定存在两个点，使得这个圆移动一下使得这两个点在圆上后，依然能够覆盖这原来N个点（详细的证明看网站上的题解，感觉还是比较intuitive的）。因此只需要遍历点对，寻找过这两个点，半径为r的圆的圆心，再计算这个圆覆盖的点数，求最大即可。注意两个点一个半径并无法确定圆心，因为这个圆心可能有两个，对称的，在纸上画画就能看出来。

然而代码写起来是有点繁杂，好多地方忘了用浮点数，debug了挺久。并且在判点是否在圆内圆外的函数中，我本地IDE上只需要>=0就行了，但这样子在leetcode网站上总有case过不了，跑出来答案不一样。于是修改了一下boundary，才通过。

完整代码

class Solution {
public:inline int calD(vector<vector<int>>& darts, int r2, double cx, double cy) {int num = 0;for (auto d : darts) {double dis2 = (d[0] - cx) * (d[0] - cx) + (d[1] - cy) * (d[1] - cy);if (r2 - dis2 >= -1e-5)num++; }return num;}int numPoints(vector<vector<int>>& darts, int r) {int n = darts.size();int ans = 1;int r2 = r*r;for (int i = 0; i < n; i++) {for (int j = i+1; j < n; j++) {double midx = 1.0*(darts[i][0] + darts[j][0]) / 2;double midy = 1.0*(darts[i][1] + darts[j][1]) / 2;double half = sqrt((darts[i][0] - darts[j][0]) * (darts[i][0] - darts[j][0]) + (darts[i][1] - darts[j][1]) * (darts[i][1] - darts[j][1]))/2;double p = sqrt(r*r - half*half);if (darts[i][0] == darts[j][0]) {ans = max(ans, calD(darts, r2, darts[i][0] + p, midy));ans = max(ans, calD(darts, r2, darts[i][0] - p, midy));}else if (darts[i][1] == darts[j][1]) {ans = max(ans, calD(darts, r2, midx, darts[i][1] + p));ans = max(ans, calD(darts, r2, midx, darts[i][1] - p));}else {double k = 1.0*(darts[i][1] - darts[j][1]) / (darts[i][0] - darts[j][0]);k = -1.0 / k;ans = max(ans, calD(darts, r2, midx + p * 1 / sqrt(1 + k*k), midy + p * k / sqrt(1 + k*k)));ans = max(ans, calD(darts, r2, midx - p * 1 / sqrt(1 + k*k), midy - p * k / sqrt(1 + k*k)));}}}return ans;}
};