Flights (解方程)
发布日期:2021-09-19 10:55:54 浏览次数:1 分类:技术文章

本文共 4290 字,大约阅读时间需要 14 分钟。

Army is busy: military exercises had started yesterday. All types of forces are doing, hopefully, a good

job. For example, artillery is launching missiles, while aviation is delivering supplies to infantry.
The military ground space is a straight line. Aviation bases and infantry regiments are located
somewhere on the line, and artillery is launching ballistic missiles everywhere. All missile launches are
planned (don’t forget, it’s just an exercise), each at a certain time along a certain trajectory. Aviation
flights are also planned in certain time and space intervals. Everything will be fine, but there are those
missiles, which can be deadly even during exercises!
You should help aviation generals to plan the minimal safe altitude for each flight. Given the
information about flight’s time and space intervals, the minimal safe altitude for a flight is the minimal
altitude such that all missile trajectories in the corresponding time and space interval are at or below
this altitude. If there are no missiles in the flight’s time and space interval, then the minimal safe
altitude is defined to be zero.
Ballistic missiles are launched from the ground, which is defined to have a zero altitude, and fly
along a vertically symmetrical parabola. Missile speed is ignored for this problem, missiles are assumed
to follow their trajectory instantaneously.
For example, the picture below shows trajectories of two ballistic missiles in solid lines, and the
minimal safe altitudes for four different flights in dashed lines. Vertical lines delimit space intervals
of each flight in this sample. Time intervals of the flights in this sample include the launch of both
missiles.
Input
The first line of input contains a single integer n — the number of missile launches planned (1 ≤ n ≤
50000).
The following n lines describe one missile launch each. Each line contains three integers: the missile
launch point p and coordinates of the highest point of missile trajectory x and y (0 ≤ p < x ≤ 50000, 0 <
y ≤ 50); p and x are coordinates along the military ground line, y gives the altitude of the highest point
of missile trajectory. Missiles are launched one by one every minute in the order they are described in
the input.
Next line contains the single integer m — the number of flights planned (1 ≤ m ≤ 20000).
The following m lines describe one flight each. Each line contains four integers: t1 and t2 (1 ≤ t1 ≤
t2 ≤ n) — the time interval for the flight, and x1 and x2 (0 ≤ x1 ≤ x2 ≤ 50000) — the space interval
for the flight along the military ground line. Time and space intervals are inclusive of their endpoints.
Time moment 1 corresponds to the first missile launch, and time moment n corresponds to the last
one.
Output
For each flight write a separate line with the minimal safe altitude, with absolute error not exceeding
10−4
.
Sample Input
2
10 30 10
20 30 30
4
1 2 0 11
1 2 20 25
1 2 25 35
1 2 45 100
2
0 10 10
30 40 10
6
1 2 0 32
1 1 19 35
2 2 0 32
1 2 15 35
1 2 21 27
1 2 2 100
Sample Output
0.975
22.5
30.0
4.375
10.0
1.9
3.6
7.5
0.0
10.0

题目大概:

给出了n个抛物线,有m条询问,每次询问第l 到第r条抛物线,在区间x1到x2的最大值是多少(最小为0)。

思路:

直接解出这n条抛物线,然后暴力求解每次询问就可以了。

代码:

#include 
using namespace std;const int maxn=5e4+10;struct poin{ double a,h,k;}p[maxn];void make(int i,double a,double b,double c){ p[i].h=b; p[i].k=c; double sum=(a-b)*(a-b); p[i].a=-(c/(sum));}double get(int i,double x){ return (p[i].a*(x-p[i].h)*(x-p[i].h)+p[i].k);}int main(){ int n,m; while(~scanf("%d",&n)) { memset(p,0,sizeof(p)); double a,b,c; for(int i=1;i<=n;i++) { scanf("%lf%lf%lf",&a,&b,&c); make(i,a,b,c); } scanf("%d",&m); int l,r; double x1,x2; for(int i=1;i<=m;i++) { scanf("%d%d%lf%lf",&l,&r,&x1,&x2); double max_1=0; for(int j=l;j<=r;j++) { if(x1>=p[j].h) { max_1=max(max_1,get(j,x1)); } else if(x2<=p[j].h) { max_1=max(max_1,get(j,x2)); } else { max_1=max(max_1,p[j].k); } } printf("%.5lf\n",max_1); } } return 0;}

转载地址:https://blog.csdn.net/a1046765624/article/details/80752530 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Potentiometers (树状数组)
下一篇:Frequent values (线段树)

发表评论

最新留言

不错!
[***.144.177.141]2024年03月19日 21时33分32秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

oracle 查询中用case,oracle case when 在查询时候的用法。 2019-04-21
oracle正在运行的程序包,ORACLE PL/SQL编程详解之程序包的创建与应用 2019-04-21
php局部页面滚动,在访问另一页面后保留浏览器滚动位置 - php 2019-04-21
jmeter运行linux命令行,Jmeter在linux上运行(命令行运行Jmeter) 2019-04-21
linux服务器怎么添加站点,如何增加站点或虚拟主机及文件说明 2019-04-21
linux系统输入指令,Linux系统基础 - 基本操作命令 2019-04-21
linux设备管理命令,Linux命令(设备管理).doc 2019-04-21
linux 中文utf-8转gbk编码,Linux平台下 GBK编码转UTF-8编码 2019-04-21
linux安装软件在boot,在Linux系统上安装Spring boot应用的教程详解 2019-04-21
linux进入用户user1主目录,Linux系统命令提示符为[user1@localhost root]当前用户所在目录为( )... 2019-04-21
取消linux自动登录,linuxdeepin 如何取消自动登录啊? 2019-04-21
linux线程存储,Linux系统编程手册:线程:线程安全和每线程存储 2019-04-21
c语言编程max,C语言编程题及答案.doc 2019-04-21
android测试页面,自动执行界面测试 | Android 开发者 | Android Developers 2019-04-21
android 图片点击变色,Android开发实现ListView点击item改变颜色功能示例 2019-04-21
android增删改查布局,Android之父_增删改查 2019-04-21
vowifi android开关,如何配置VoLTE, ViLTE and VoWifi(IMS config for VoLTE, ViLTE and VoWifi) 2019-04-21
电脑端的mafsvr服务关掉_网吧才是电脑优化的精髓!学会3招你也不用羡慕网吧的流畅了... 2019-04-21
html获取文件路径_HTML 文件路径 2019-04-21
mysql滴的一声就关了_关于mysql数据库在输入密码后,滴的一声直接退出界面的解决办法(详细办法)... 2019-04-21