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

2020 杭电多校第三场 H Triangle Collision(反射套路 + 绕点旋转 + 矢量

2020 杭电多校第三场 H. Triangle Collision(反射套路 + 绕点旋转 + 矢量分解)

大意:给出一个等边三角形 , 以底边中线建立坐标系 , 给出三角形中一点 , 和其初始速度 , 小球在等边三角形中做完全弹性碰撞 , 问其恰好碰撞 k 次的时间。

解法:

trick1: 反射套路

对于这样一个反射套路题 , 如果模拟在一个三角形内模拟碰撞的话 , 显然不现实 ,所以我们可以根据反射原理 , 将路径变成一条直线。这样问题就变成了射线在下图中的交点个数问题。

在这里插入图片描述

trick2: 我们不妨先思考水平直线相交个数如何求。假设运动实现为 t 那么显然交点个数就是

a b s ( f l o o r ( y + v y t h ) ) abs(floor(\frac{y+v_yt}{h})) abs(floor(hy+vyt))

对于另外两种直线 , 我们要求相应坐标系下的 y 和 vy

对于 y(标量) 的求法有两种 , 第一种是用点到直线的距离公式 , 但是点到直线距离公式中有除法 , 误差很大 , 所以精度不够。

第二种方法是我们可以把操作转化成绕三角形中心旋转坐标系 , 对应点的坐标也绕中心旋转后即是答案。

trick3:

对于 vy(矢量) , 我们设立好正方向 , 进行矢量分解即可。一定要设立正方向 , 因为矢量是有方向的。

这样就能求得某一时刻 t 穿过点数量 , 二分一下 t 即可。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;//--------------------------------------------------------------
const double eps = 1e-5;
const double pi = acos(-1);
inline double sqr(double x) {return x * x;} //平方
int sign(double x){if(fabs(x) < eps) return 0;if(x > 0) return 1;return -1;
}//符号
struct point{double x , y;point(){}point(double a , double b) : x(a) , y(b){}friend point operator + (const point &a , const point &b){return point(a.x + b.x , a.y + b.y);}friend point operator - (const point &a , const point &b){return point(a.x - b.x , a.y - b.y);}friend bool operator == (const point &a , const point &b){return !sign(a.x - b.x) && !sign(a.y - b.y);}friend point operator * (const point &a , const double &b){return point(a.x * b , a.y * b);}friend point operator * (const double &a , const point &b){return point(a * b.x , a * b.y);}friend point operator / (const point &a , const double &b){return point(a.x / b , a.y / b);}//向量模长 double norm(){ return sqrt(sqr(x) + sqr(y));}
}; //坐标轴绕某点旋转后 , 原坐标轴下的点也会绕这个点旋转
double rotate_point(const point &a , const point &p , double A){double tx = p.x - a.x , ty = p.y - a.y;return a.y + tx * sin(A) + ty * cos(A);
}// p 点 绕 a 点逆时针旋转 A 弧度
//--------------------------------------------------------------int t , k;
double h , x , y , vx , vy , yr , yl;int solve(double st , double v , double t){return abs(floor((st + v * t) / h));
}bool check(double t){int res = 0;res += solve(y , vy , t);//水平res += solve(yr , (vx * sqrt(3) - vy) / 2 , t);res += solve(yl , (-vx * sqrt(3) - vy) / 2 , t);return res >= k;
}signed main(){cout << fixed << setprecision(10);cin >> t;while(t --){cin >> h >> x >> y >> vx >> vy >> k;h = h * sqrt(3) / 2;yr = rotate_point(point{0 , h / 3} , point{x , y} , pi / 3 * 2);yl = rotate_point(point{0 , h / 3} , point{x , y} , pi / 3 * 4);double l = 0 , r = 1e9 , mid = 0;while(r - l > eps){mid = (l + r) / 2;if(check(mid)) r = mid;else l = mid;}cout << mid << "\n";		}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

相关文章:

2020 杭电多校第三场 H Triangle Collision(反射套路 + 绕点旋转 + 矢量

2020 杭电多校第三场 H. Triangle Collision(反射套路 绕点旋转 矢量分解) 大意&#xff1a;给出一个等边三角形 &#xff0c; 以底边中线建立坐标系 &#xff0c; 给出三角形中一点 &#xff0c; 和其初始速度 &#xff0c; 小球在等边三角形中做完全弹性碰撞 &#xff0c; …...

Servlet属性、监听者和会话

没有servlet能单独存在。在当前的现代Web应用中&#xff0c;许多组件都是在一起协作共同完成一个目标。怎么让这些组件共享信息&#xff1f;如何隐藏信息&#xff1f;怎样让信息做到线程安全&#xff1f; 1 属性和监听者 1.1 初始化 容器初始化一个servlet时&#xff0c;会为…...

Gin学习记录2——路由

路由 一. 常规路由二. 动态路由三. 带参数的路由3.1 GET3.2 POST3.3 绑定 四. 简单的路由组五. 文件分组 一. 常规路由 package mainimport ("net/http""github.com/gin-gonic/gin" )func index(ctx *gin.Context) {ctx.String(http.StatusOK, "Hell…...

《计算机算法设计与分析》第一章:算法概述

第一章 算法概述 1.1 算法复杂性分析 公共标准&#xff1a;渐进时间复杂度 &#xff08;1&#xff09;大O表示法&#xff1a; 例如&#xff1a; 大O表示法和前面的最坏时间复杂度的区别在于&#xff1a;大O表示法表示的更为简洁&#xff0c; 而最坏时间复杂度相对就比较繁琐&am…...

华为数通方向HCIP-DataCom H12-821题库(单选题:201-220)

第201题 BGP 协议用​​ beer default-route-advertise​​ 命令来给邻居发布缺省路由,那么以下关于本地 BGP 路由表变化的描述&#xff0c;正确的是哪一项? A、在本地 BGP 路由表中生成一条活跃的缺省路由并下发给路由表 B、在本地 BGP 路由表中生成一条不活跃的缺省路由&…...

使用ELK收集解析nginx日志和kibana可视化仪表盘

文章目录 ELK生产环境配置filebeat 配置logstash 配置 kibana仪表盘配置配置nginx转发ES和kibanaELK设置账号和密码 ELK生产环境配置 ELK收集nginx日志有多种方案&#xff0c;一般比较常见的做法是在生产环境服务器搭建filebeat 收集nginx的文件日志并写入到队列&#xff08;k…...

【Sentinel】ProcessorSlotChain处理器插槽链与Node

文章目录 1、Sentinel的基本概念2、ProcessorSlotChain3、Node 1、Sentinel的基本概念 Sentinel实现限流、隔离、降级、熔断等功能&#xff0c;本质要做的就是两件事情&#xff1a; 统计数据&#xff1a;统计某个资源的访问数据&#xff08;QPS、RT等信息&#xff09;规则判断…...

数据库管理系统(DBMS)的事务四大特性(ACID)以及事务的四种隔离级别

一、什么是ACID&#xff1f; ACID是原子性&#xff08;Atomicity&#xff09;、一致性&#xff08;Consistency&#xff09;、隔离性&#xff08;Isolation&#xff09;和持久性&#xff08;Durability&#xff09; 的缩写&#xff0c;是在可靠数据库管理系统&#xff08;DBMS&…...

leetcode 234. 回文链表

2023.9.5 本题先将链表的节点值移到数组中&#xff0c;再用双指针去判断该数组是否为回文的即可。 代码如下&#xff1a; /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* …...

Scala集合继承体系图

Scala集合简介 1&#xff09; Scala 的集合有三大类&#xff1a;序列 Seq、集Set、映射 Map&#xff0c;所有的集合都扩展自 Iterable特质。 2&#xff09; 对于几乎所有的集合类&#xff0c;Scala 都同时提供了可变和不可变的版本&#xff0c;分别位于以下两个包 不可变集合…...

《Go 语言第一课》课程学习笔记(十五)

并发 Go 的并发方案&#xff1a;goroutine 并行&#xff08;parallelism&#xff09;&#xff0c;指的就是在同一时刻&#xff0c;有两个或两个以上的任务&#xff08;这里指进程&#xff09;的代码在处理器上执行。 并发不是并行&#xff0c;并发关乎结构&#xff0c;并行关…...

练习 Qt 实时显示鼠标坐标位置

Qt 入门实战教程&#xff08;目录&#xff09; 前驱课程 本文是文章 Qt鼠标点击事件处理&#xff1a;显示鼠标点击位置&#xff08;完整示例&#xff09; 的一个作业&#xff08;下文称之为“前驱课程”&#xff09;。 前驱课程中&#xff0c;我们完整的展示了如何在QtCreat…...

Leetcode130. 被围绕的区域

Every day a Leetcode 题目来源&#xff1a;130. 被围绕的区域 本题给定的矩阵中有三种元素&#xff1a; 字母 X&#xff1b;被字母 X 包围的字母 O&#xff1b;没有被字母 X 包围的字母 O。 本题要求将所有被字母 X 包围的字母 O都变为字母 X &#xff0c;但很难判断哪些 …...

6.xpath的基本使用

xpath是python做数据解析的库 目录 1 安装 2 解析本地的html文件 2.1 只有一个标签的情况 2.2 有多个标签的情况 3 解析网上的页面 4 xpath表达式 4.1 绝对路径 4.2 两个斜杠表示中间隔了0级或多级 4.3 通过属性查找 4.4 通过索引查找 4.5 获取文本内容…...

uniapp组件库总结笔记

uView-ui uView 2.0 - 全面兼容 nvue 的 uni-app 生态框架 - uni-app UI 框架 优点&#xff1a;整体样式风格不错 缺点&#xff1a;不支持vue3&#xff08;可以使用社区维护的uview-plus uview-plus 3.0 - 全面兼容nvue的uni-app生态框架 - uni-app UI框架&#xff09; uni-u…...

day-42 代码随想录算法训练营 动态规划 part 04

416.分割等和子集 分析&#xff1a;需要总和能分成两半&#xff0c;并且有子集能装满一半 思路&#xff1a; 1.dp存储&#xff1a;容量为j时装入的最大数值和dp[j]2.dp[j]max(dp[j],dp[j-nums[i]]nums[i]) 3.全部初始化为04.遍历顺序&#xff1a;外层遍历元素&#xff0c;内…...

Swift 周报 第三十六期

文章目录 前言新闻和社区消息称苹果公司和印度财政部官员磋商&#xff0c;扩大在印度的制造产能iPhone 15 Pro 机型新增泰坦灰iPhone 15 全系配 USB-C 苹果拒绝接口和安卓互通 提案正在审查的提案 Swift论坛推荐博文话题讨论关于我们 前言 本期是 Swift 编辑组整理周报的第三十…...

手写Mybatis:第19章-二级缓存

文章目录 一、目标&#xff1a;二级缓存二、设计&#xff1a;二级缓存三、实现&#xff1a;二级缓存3.1 工程结构3.2 二级缓存类图3.3 二级缓存队列3.3.1 FIFI缓存策略3.3.2 事务缓存3.3.3 事务管理3.3.4 修改一级缓存 3.4 缓存执行器3.4.1 执行器接口3.4.2 执行器抽象基类3.4.…...

Alibaba Canal 使用记录

项目中使用 canal 来同步数据到 Elasticsearch, 遇到很多问题&#xff0c;做一下记录&#xff1a; 版本问题&#xff1a; 1. 解析binlog出错 &#xff0c;表现为 limit excceed&#xff1a;xx 目前使用 mariadb 10.9.7/10.10.6 canal 1.1.6 hotfix &#xff0c;在这个版本组…...

GIT实战篇,教你如何使用GIT可视化工具

系列文章目录 手把手教你安装Git&#xff0c;萌新迈向专业的必备一步 GIT命令只会抄却不理解&#xff1f;看完原理才能事半功倍&#xff01; 快速上手GIT命令&#xff0c;现学也能登堂入室 GIT实战篇&#xff0c;教你如何使用GIT可视化工具 系列文章目录一、GIT有哪些常用工具…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...