hdu5033 最大仰望角

网友投稿 629 2022-10-30

hdu5033 最大仰望角

hdu5033 最大仰望角

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

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

#include#include#include#include#include#includeusing 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); setmy_st; mapmark; 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：数据
上一篇:Nearly 是一个轻量, 高效, 简洁的数据流框架;
下一篇:23种设计模式总结
相关文章

 发表评论

暂时没有评论，来抢沙发吧~