hdu5033 最大仰望角

期望值最大化: 优化决策以达到最大期望收益 #生活技巧# #领导力技巧# #决策模型#

生活随笔 收集整理的这篇文章主要介绍了 hdu5033 最大仰望角 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

题意：
      给你n个楼房排成一条直线，楼房可以看成是宽度为1的线段，然后给你m组询问，每组询问给你一个坐标，输出在当前坐标仰望天空的可视角度。

思路：

      n比较大，O(n*m)肯定跪，其实我们可以优化掉凹形的时候，比如当前询问点为x,对于右侧，往右跑的时候，我们只跑升序的就行了，这样我们只要开一个数组记录当前点最近的右侧的上升点就行了，到达当前点的时候，如果不满足，可以直接跳到记录的那个点上去，比赛的时候没敢敲，感觉时间根本过不去，后来听说可以，我又重新敲了一下，结果AC了，感觉应该是随机数据的原因，也就是根本达不到O(n*m).还有，找小标的时候可以用二分去找，刚才写的时候脑袋一热突然就用容器去弄的，就是开了一个set和一个map，一个找值一个哈希值（不建议这样写，二分就行了，还省时间）。具体看代码。

#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<set> #include<map> using namespace std;typedef struct {double X ,Y; }Point;typedef struct {double x ,h; }NODE;NODE node[110000]; int merl[110000]; int merr[110000];bool camp(NODE a ,NODE b) {return a.x < b.x; }int main () {int t ,i ,j ,n ,m ,cas = 1;double x;scanf("%d" ,&t);while(t--){scanf("%d" ,&n);set<double>my_st;map<double ,int>mark;my_st.clear();mark.clear();for(i = 1 ;i <= n ;i ++){scanf("%lf %lf" ,&node[i].x ,&node[i].h);merl[i] = merr[i] = i;}sort(node + 1 ,node + n + 1 ,camp);for(i = 1 ;i <= n ;i ++){my_st.insert(node[i].x);mark[node[i].x] = i;}for(i = 1 ;i <= n ;i ++){for(j = i - 1 ;j >= 1 ;j --){if(node[j].h > node[i].h){merl[i] = j; break;}if(j == merl[j]) break;}}for(i = n ;i >= 1 ;i --){for(j = i + 1 ;j <= n ;j ++){if(node[j].h > node[i].h){merr[i] = j;break;}if(j == merr[j]) break;}}scanf("%d" ,&m);printf("Case #%d:\n" ,cas ++);while(m--){scanf("%lf" ,&x);int r = mark[*my_st.lower_bound(x)];int l = r - 1;double max = node[r].h * 1.0 / (node[r].x - x);int idr = r;while(merr[r] != r){r = merr[r];if(max < node[r].h * 1.0 / (node[r].x - x)){max = node[r].h * 1.0 / (node[r].x - x);idr = r;}}max = node[l].h * 1.0 / (x - node[l].x);int idl = l;while(merl[l] != l){ l = merl[l];if(max < node[l].h * 1.0 / (x - node[l].x)){max = node[l].h * 1.0 / (x - node[l].x);idl = l;}} Point A ,B ,C;A.X = node[idl].x ,A.Y = node[idl].h;B.X = x ,B.Y = 0;C.X = node[idr].x ,C.Y = node[idr].h;double x1 = A.X - x ,y1 = A.Y;double x2 = C.X - x ,y2 = C.Y;double Ang = ((x1 * x2) + (y1 * y2)) / (sqrt(x1 * x1 + y1 * y1) * sqrt(x2 * x2 + y2 * y2));Ang = acos(Ang);printf("%.10lf\n" ,Ang * 180.0 / acos(-1.0));}}return 0; }

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的hdu5033 最大仰望角的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。

网址：hdu5033 最大仰望角 https://www.yuejiaxmz.com/news/view/1250054

相关内容

仰望生活的情感抒写
7’17”900，仰望U9纽北圈速含金量究竟有多高？
望岳谈｜“山东好品”魅力源泉：脚踏实地和仰望星空
仰望智能语音硬核进阶，当之无愧业内第一梯队
为4轮边电机主动冷却！仰望U7全新一体化热管理技术优势
仰望U7的电池和热管理技术有什么独到之处？
一城仰望，仅18席！福天·滨江院子13#鼎级新品加推，再掀争藏热潮！
中信银行“少年看中国”2025年度活动开启 首站带少年“仰望星空”
仰望u8油耗是多少？它的节能措施具体包括哪些方面？
中信银行“少年看中国”2025年度活动开启， 首站带少年“仰望星空”

随便看看