南昌网站建设模板服务商,电子商城开发网站建设,做美食网站,临沂做商城网站建设1. 题目
墙壁上挂着一个圆形的飞镖靶。现在请你蒙着眼睛向靶上投掷飞镖。
投掷到墙上的飞镖用二维平面上的点坐标数组表示。飞镖靶的半径为 r 。
请返回能够落在 任意 半径为 r 的圆形靶内或靶上的最大飞镖数。
示例 1#xff1a;
输入#xff1a;points [[-2,0],[2,0…1. 题目
墙壁上挂着一个圆形的飞镖靶。现在请你蒙着眼睛向靶上投掷飞镖。
投掷到墙上的飞镖用二维平面上的点坐标数组表示。飞镖靶的半径为 r 。
请返回能够落在 任意 半径为 r 的圆形靶内或靶上的最大飞镖数。
示例 1
输入points [[-2,0],[2,0],[0,2],[0,-2]], r 2
输出4
解释如果圆形的飞镖靶的圆心为 (0,0) 半径为 2
所有的飞镖都落在靶上此时落在靶上的飞镖数最大值为 4 。示例 2
输入points [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r 5
输出5
解释如果圆形的飞镖靶的圆心为 (0,4) 半径为 5
则除了 (7,8) 之外的飞镖都落在靶上此时落在靶上的飞镖数最大值为 5 。示例 3
输入points [[-2,0],[2,0],[0,2],[0,-2]], r 1
输出1示例 4
输入points [[1,2],[3,5],[1,-1],[2,3],[4,1],[1,3]], r 2
输出4提示
1 points.length 100
points[i].length 2
-10^4 points[i][0], points[i][1] 10^4
1 r 5000来源力扣LeetCode 链接https://leetcode-cn.com/problems/maximum-number-of-darts-inside-of-a-circular-dartboard 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题 class Solution {double cx, cy;//圆心坐标
public:int numPoints(vectorvectorint points, int r) {int x1, x2, y1, y2;double dx, dy;int i, j, k, count, maxcount1, n points.size();for(i 0; i n; i){x1 points[i][0];y1 points[i][1];for(j i1; j n; j)//i,j为圆上的点{if(i j)continue;x2 points[j][0];y2 points[j][1];count 2;int d_d (x1-x2)*(x1-x2)(y1-y2)*(y1-y2);if(d_d 4*r*r) continue;count 0;cx (x1x2)/2.0-(y2-y1)*sqrt((r*r-d_d/4.0)/d_d), cy (y1y2)/2.0(x2-x1)*sqrt((r*r-d_d/4.0)/d_d);for(k 0; k n; k){dx points[k][0]-cx;dy points[k][1]-cy;if(dx*dxdy*dy r*r)count;}maxcount max(maxcount, count);count 0;cx (x1x2)/2.0(y2-y1)*sqrt((r*r-d_d/4.0)/d_d), cy (y1y2)/2.0-(x2-x1)*sqrt((r*r-d_d/4.0)/d_d);for(k 0; k n; k){dx points[k][0]-cx;dy points[k][1]-cy;if(dx*dxdy*dy r*r)count;}maxcount max(maxcount, count);}}return maxcount;}
};52 ms 8 MB
