题目：Building
题意：坐标轴上N个建筑物，忽略宽度只计高度，然后查询的是，当人的坐标为qi时，人抬头能看到的天空的角度有多大。即有多大的角度是没有被建筑物遮挡到的。人的高度视为0。
一看到这题就想到了单调队列维护个最优方案，最后写出来其实是个单调栈。这个保证从栈底到栈顶是建筑物高度从小到大从大到小的。
对于这个问题，我们可以分成两边处理。求出左边被遮挡的角度，再求出右边被遮挡的角度，用180减去这两个就是答案。而左边会求，右边自然也会求。
把查询都读入之后，放一个结构体，id为0表示建筑物，大于0的对应查询的编号。按照x从小到大排序。
接着从左往右扫，遇到建筑物的，做添加，添加的时候维护下栈：
当前栈顶元素是top-1的位置，top=0表示空。如果当前的建筑物比栈顶的高，那肯定当前建筑物更有可能挡住后面的查询，删除栈顶元素直到它的高度比当前的高。
但是这样还不够，假设当前建筑物A，栈顶是B，B下面是C。如果站在A的顶端，A能够看到C，即不会被B挡住，B也不会在挡住后面的视线。
原因是，我们可以从B顶端连接A一直到地面交点D，显然在D以及D左边的，看不到B，会被A挡住，而在D右边的，此时虽然能看到B，但是后面的C更能挡住它，如下图所示：
所以B不会挡住后面，可以把B删掉。
而如果遇到查询的，也是要看下当前栈顶是不是最优。还是那上图，经过我们上面的维护，现在栈顶是A，A下面是C。
如果遇到查询是只能看到A不能看到C，，那么就由A算即可。
而如果能看到C，应该把A删去，因为此时A也不可能挡住更往后的查询。删完之后如果栈内还有多个元素，比如C下面还有E，还要继续比较。
左边求完了，右边也类似。
复杂度的话，每个元素都是进入栈两次，出来两次，因为是左右各一次，每次查询取栈顶，复杂度O(N)。
#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;const int N = 200010;const double PI = acos(-1.0);double ans[N], X[N], H[N];struct Point{double x, h;int id;bool operator < (const Point &A)const{return x<A.x;}}p[N];int T, n, q;void cal(int st, int ed, int d){int top=0;for(int i=st; i!=ed; i+=d){if(p[i].id){while(top>1){double k1 = H[top-1]/fabs(p[i].x-X[top-1]);double k2 = H[top-2]/fabs(p[i].x-X[top-2]);if(k1<=k2) top–;else break;}ans[p[i].id] += atan(H[top-1]/fabs(p[i].x-X[top-1]));}else{X[top] = p[i].x;H[top] = p[i].h;while(top && H[top]>=H[top-1]){top–;H[top]=H[top+1];X[top]=X[top+1];}while(top>1){double k1 = (H[top-1]-H[top])/fabs(X[top-1]-X[top]);double k2 = (H[top-2]-H[top])/fabs(X[top-2]-X[top]);if(k1<=k2){top–;H[top] = H[top+1];X[top] = X[top+1];}else break;}top++;}}}int main(){scanf("%d", &T);for(int t=1; t<=T; t++){scanf("%d", &n);for(int i=0; i<n; i++){scanf("%lf %lf", &p[i].x, &p[i].h);p[i].id = 0;}scanf("%d", &q);for(int i=0; i<q; i++){scanf("%lf", &p[n].x);p[n].h = 0.0;p[n].id = i+1;ans[i+1]=0.0;n++;}sort(p, p+n);cal(0, n, 1);cal(n-1, -1, -1);printf("Case #%d:\n", t);for(int i=1; i<=q; i++) printf("%.10f\n", (PI-ans[i])*180.0/PI);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
敏而好学，不耻下问。
