内部网站开发软件,网页制作平台哪家好,网站建设的小说,广州广告公司有哪些题目链接#xff1a;https://leetcode.cn/problems/maximum-number-of-darts-inside-of-a-circular-dartboard/description/
题目大意#xff1a;给出一系列点和一个圆的半径#xff0c;#xff08;寻找一个圆心#xff09;求这个半径的圆最多能覆盖多少个点。
思路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(vectorvectorint 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(vectorvectorint darts, int r) {int n darts.size();int ans 1;int r2 r*r;for (int i 0; i n; i) {for (int j i1; 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;}
};
