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

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

题目链接: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;}
};

相关文章:

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

题目链接&#xff1a;https://leetcode.cn/problems/maximum-number-of-darts-inside-of-a-circular-dartboard/description/ 题目大意&#xff1a;给出一系列点和一个圆的半径&#xff0c;&#xff08;寻找一个圆心&#xff09;求这个半径的圆最多能覆盖多少个点。 思路&…...

啤酒:从饮品到文化的演变

在人类饮品的长河中&#xff0c;啤酒以其不同的魅力走过了一段漫长的历史旅程。它不仅仅是一种简单的饮品&#xff0c;更是一种文化的象征&#xff0c;一种生活的态度。今天&#xff0c;我们将一起追溯啤酒从单一的饮品到丰富文化的演变过程&#xff0c;并感受Fendi Club精酿啤…...

Java 中 Map 常用类和数据结构详解

1. 引言 在Java编程中&#xff0c;Map是一种重要的数据结构&#xff0c;广泛应用于各种场景&#xff0c;Map实现了键值对&#xff08;key-value&#xff09;的存储方式&#xff0c;使得开发者能够快速检索、更新和操作数据。本篇文章将详细讲解Java中常用的Map类及其底层数据结…...

实时监控,动态调整 —— 淘宝商品详情API助力商家实现灵活经营

在讨论实时监控和动态调整的策略时&#xff0c;虽然我不能直接提供淘宝商品详情API的具体代码&#xff08;因为这通常涉及商业机密和API密钥等敏感信息&#xff09;&#xff0c;但我可以给出一个概念性的示例&#xff0c;说明如何使用这类API来辅助商家实现灵活经营。 概念性示…...

WebGL常用接口和事件

目录 初始化WebGL上下文清除缓冲区缓冲区对象着色器和程序属性指针渲染事件监听错误处理纹理映射...

Golang | Leetcode Golang题解之第429题N叉树的层序遍历

题目&#xff1a; 题解&#xff1a; func levelOrder(root *Node) (ans [][]int) {if root nil {return}q : []*Node{root}for q ! nil {level : []int{}tmp : qq nilfor _, node : range tmp {level append(level, node.Val)q append(q, node.Children...)}ans append(a…...

数据库的全透明加密和半透明加密主要是针对数据存储安全的不同处理方式

数据库的全透明加密和半透明加密主要是针对数据存储安全的不同处理方式。 全透明加密&#xff08;也称作无损加密或自动加密&#xff09;就像是给文字戴上了一层无形的面具。在用户看来&#xff0c;他们在数据库中输入的是明文&#xff08;比如姓名、密码&#xff09;&#xf…...

MySQL的登录、访问、退出

一、登录&#xff1a; 访问MySQL服务器对应的命令&#xff1a;mysql.exe ,位置&#xff1a;C:\Program Files\MySQL\MySQL Server 8.0\bin &#xff08;mysql.exe需要带参数执行&#xff0c;所以直接在图形界面下执行该命令会自动结束&#xff09; 执行mysql.exe命令的时候出…...

计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-09-25

计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-09-25 1. PromSec: Prompt Optimization for Secure Generation of Functional Source Code with Large Language Models (LLMs) M Nazzal, I Khalil, A Khreishah, NH Phan - arXiv preprint arXiv:2409.12699, 2…...

PyTorch框架安装

安装 pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple 介绍 PyTorch 一个 Python 深度学习框架&#xff0c;它将数据封装成张量&#xff08;Tensor&#xff09;来进行处理。 PyTorch 中的张量就是元素为 同一种数据 类型的多维矩阵。在 PyTorch 中&#xff0…...

分布式锁优化之 使用lua脚本改造分布式锁保证判断和删除的原子性(优化之LUA脚本保证删除的原子性)

文章目录 1、lua脚本入门1.1、变量&#xff1a;弱类型1.2、流程控制1.3、在lua中执行redis指令1.4、实战&#xff1a;先判断是否自己的锁&#xff0c;如果是才能删除 2、AlbumInfoApiController --》testLock()3、AlbumInfoServiceImpl --》testLock() 1、lua脚本入门 Lua 教程…...

从安防视频监控行业发展趋势看EasyCVR平台如何驱动行业智能升级

一、市场规模持续增长 随着科技的进步和社会安全意识的提升&#xff0c;安防视频监控行业市场规模持续增长。据市场研究数据显示&#xff0c;全球智能视频监控市场规模已超过千亿美元&#xff0c;并有望在未来几年内保持高速增长。在中国市场&#xff0c;随着智慧城市、工业互…...

TIOBE 编程指数 9 月排行榜公布 VB.Net第七

原文地址&#xff1a;百度安全验证 IT之家 9 月 8 日消息&#xff0c;TIOBE 编程社区指数是一个衡量编程语言受欢迎程度的指标&#xff0c;评判的依据来自世界范围内的工程师、课程、供应商及搜索引擎&#xff0c;今天 TIOBE 官网公布了 2024 年 9 月的编程语言排行榜&#xf…...

如何用ChatGPT制作一款手机游戏应用

有没有想过自己做一款手机游戏&#xff0c;并生成apk手机应用呢&#xff1f;有了人工智能&#xff0c;这一切就成为可能。今天&#xff0c;我们就使用ChatGPT来创建一个简单的井字棋游戏&#xff08;Tic-Tac-Toe&#xff09;&#xff0c;其实这个过程非常轻松且高效。 通过Cha…...

0基础学前端 day4

大家好&#xff0c;欢迎来到无限大的频道。 今天继续带领大家开始0基础学前端。 一、 什么是Bootstrap框架&#xff1f; Bootstrap是一个开源前端框架&#xff0c;于2011年由Twitter的开发团队开发并发布。其主要目的是简化开发过程&#xff0c;并使开发者能够轻松快速地构建…...

功能测试详解

&#x1f345; 点击文末小卡片&#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 一、测试项目启动与研读需求文档 &#xff08;一&#xff09; 组建测试团队 1、测试团队中的角色 2、测试团队的基本责任 尽早地发现软件程序、系统或产品中所…...

<Java>String类型变量的使用

两边有一个string就是连接&#xff0c;否则做加法 ‘ ’是char&#xff0c;“ ”是string&#xff0c;char能做加法&#xff0c;string只能连接...

JavaScript可视化

JavaScript 提供了多种库和工具来进行数据可视化。以下是一些流行的可视化库及其特点: D3.js特点: 强大的数据驱动文档(Data-Driven Documents)库,允许创建复杂的交互式图表。使用场景: 适合需要高度自定义和复杂交互的可视化。Chart.js特点: 易于使用的图表库,提供了多种…...

HTML5简介的水果蔬菜在线商城网站源码系列模板3

文章目录 1.设计来源1.1 主界面1.2 商品列表1.3 商品信息1.4 购物车1.5 其他页面效果 2.效果和源码2.1 动态效果2.2 源代码 源码下载万套模板&#xff0c;程序开发&#xff0c;在线开发&#xff0c;在线沟通 作者&#xff1a;xcLeigh 文章地址&#xff1a;https://blog.csdn.ne…...

传输层TCP协议

一、TCP协议格式 我们看到报头固定有20字节&#xff0c;最后选项大小不固定。 4位首部长度&#xff08;二进制0000 ~ 1111&#xff0c;十进制范围[0, 15]&#xff09;单位是4字节&#xff08;存放字节大小范围[0, 60]&#xff09;包括了20字节固定长度 选项长度。若选项大小为…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...