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 locatedsomewhere on the line, and artillery is launching ballistic missiles everywhere. All missile launches areplanned (don’t forget, it’s just an exercise), each at a certain time along a certain trajectory. Aviationflights are also planned in certain time and space intervals. Everything will be fine, but there are thosemissiles, which can be deadly even during exercises!You should help aviation generals to plan the minimal safe altitude for each flight. Given theinformation about flight’s time and space intervals, the minimal safe altitude for a flight is the minimalaltitude such that all missile trajectories in the corresponding time and space interval are at or belowthis altitude. If there are no missiles in the flight’s time and space interval, then the minimal safealtitude is defined to be zero.Ballistic missiles are launched from the ground, which is defined to have a zero altitude, and flyalong a vertically symmetrical parabola. Missile speed is ignored for this problem, missiles are assumedto follow their trajectory instantaneously.For example, the picture below shows trajectories of two ballistic missiles in solid lines, and theminimal safe altitudes for four different flights in dashed lines. Vertical lines delimit space intervalsof each flight in this sample. Time intervals of the flights in this sample include the launch of bothmissiles.InputThe 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 missilelaunch 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 pointof missile trajectory. Missiles are launched one by one every minute in the order they are described inthe 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 intervalfor 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 lastone.OutputFor each flight write a separate line with the minimal safe altitude, with absolute error not exceeding10−4.Sample Input210 30 1020 30 3041 2 0 111 2 20 251 2 25 351 2 45 10020 10 1030 40 1061 2 0 321 1 19 352 2 0 321 2 15 351 2 21 271 2 2 100Sample Output0.97522.530.04.37510.01.93.67.50.010.0题目大概:
给出了n个抛物线,有m条询问,每次询问第l 到第r条抛物线,在区间x1到x2的最大值是多少(最小为0)。
思路:
直接解出这n条抛物线,然后暴力求解每次询问就可以了。
代码:
#includeusing 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.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
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自动登录,linuxdeepin 如何取消自动登录啊?
2019-04-21
linux线程存储,Linux系统编程手册:线程:线程安全和每线程存储
2019-04-21
c语言编程max,C语言编程题及答案.doc
2019-04-21
android增删改查布局,Android之父_增删改查
2019-04-21
html获取文件路径_HTML 文件路径
2019-04-21