【几何】个人练习-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
题目链接:https://leetcode.cn/problems/maximum-number-of-darts-inside-of-a-circular-dartboard/description/ 题目大意:给出一系列点和一个圆的半径,(寻找一个圆心)求这个半径的圆最多能覆盖多少个点。 思路&…...

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

Java 中 Map 常用类和数据结构详解
1. 引言 在Java编程中,Map是一种重要的数据结构,广泛应用于各种场景,Map实现了键值对(key-value)的存储方式,使得开发者能够快速检索、更新和操作数据。本篇文章将详细讲解Java中常用的Map类及其底层数据结…...
实时监控,动态调整 —— 淘宝商品详情API助力商家实现灵活经营
在讨论实时监控和动态调整的策略时,虽然我不能直接提供淘宝商品详情API的具体代码(因为这通常涉及商业机密和API密钥等敏感信息),但我可以给出一个概念性的示例,说明如何使用这类API来辅助商家实现灵活经营。 概念性示…...
WebGL常用接口和事件
目录 初始化WebGL上下文清除缓冲区缓冲区对象着色器和程序属性指针渲染事件监听错误处理纹理映射...

Golang | Leetcode Golang题解之第429题N叉树的层序遍历
题目: 题解: 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…...
数据库的全透明加密和半透明加密主要是针对数据存储安全的不同处理方式
数据库的全透明加密和半透明加密主要是针对数据存储安全的不同处理方式。 全透明加密(也称作无损加密或自动加密)就像是给文字戴上了一层无形的面具。在用户看来,他们在数据库中输入的是明文(比如姓名、密码)…...

MySQL的登录、访问、退出
一、登录: 访问MySQL服务器对应的命令:mysql.exe ,位置:C:\Program Files\MySQL\MySQL Server 8.0\bin (mysql.exe需要带参数执行,所以直接在图形界面下执行该命令会自动结束) 执行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 深度学习框架,它将数据封装成张量(Tensor)来进行处理。 PyTorch 中的张量就是元素为 同一种数据 类型的多维矩阵。在 PyTorch 中࿰…...

分布式锁优化之 使用lua脚本改造分布式锁保证判断和删除的原子性(优化之LUA脚本保证删除的原子性)
文章目录 1、lua脚本入门1.1、变量:弱类型1.2、流程控制1.3、在lua中执行redis指令1.4、实战:先判断是否自己的锁,如果是才能删除 2、AlbumInfoApiController --》testLock()3、AlbumInfoServiceImpl --》testLock() 1、lua脚本入门 Lua 教程…...

从安防视频监控行业发展趋势看EasyCVR平台如何驱动行业智能升级
一、市场规模持续增长 随着科技的进步和社会安全意识的提升,安防视频监控行业市场规模持续增长。据市场研究数据显示,全球智能视频监控市场规模已超过千亿美元,并有望在未来几年内保持高速增长。在中国市场,随着智慧城市、工业互…...

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

如何用ChatGPT制作一款手机游戏应用
有没有想过自己做一款手机游戏,并生成apk手机应用呢?有了人工智能,这一切就成为可能。今天,我们就使用ChatGPT来创建一个简单的井字棋游戏(Tic-Tac-Toe),其实这个过程非常轻松且高效。 通过Cha…...
0基础学前端 day4
大家好,欢迎来到无限大的频道。 今天继续带领大家开始0基础学前端。 一、 什么是Bootstrap框架? Bootstrap是一个开源前端框架,于2011年由Twitter的开发团队开发并发布。其主要目的是简化开发过程,并使开发者能够轻松快速地构建…...

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

<Java>String类型变量的使用
两边有一个string就是连接,否则做加法 ‘ ’是char,“ ”是string,char能做加法,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 源代码 源码下载万套模板,程序开发,在线开发,在线沟通 作者:xcLeigh 文章地址:https://blog.csdn.ne…...

传输层TCP协议
一、TCP协议格式 我们看到报头固定有20字节,最后选项大小不固定。 4位首部长度(二进制0000 ~ 1111,十进制范围[0, 15])单位是4字节(存放字节大小范围[0, 60])包括了20字节固定长度 选项长度。若选项大小为…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...

Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...

初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...