题意： 给你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;}
【本文由：高防cdn gfcdn.html 复制请保留原URL】人之所以有一张嘴，而有两只耳朵，原因是听的要比说的多一倍。
