HDU 5033 Building (维护单调栈)

题意：n个建筑物，Q条询问，问所在的位置，看到天空的角度是多少，每条询问的位置左右必定是有建筑物的。

思路：维护一个单调栈，将所有的建筑物和所有的人都放到一起开始算就行，每加入一个人，就维护栈里的建筑物的高度，也就是说这个人所能够看到的建筑物时在栈里的，但是这个人看不到的就删掉，例如下图，中间三个点可以删掉了，因为角度问题中间三个是看不到的，所以不会影响最终求得角度

还有一种情况，就是下述的情况，不停的维护单调栈，人站在不同的地方角度也是不一样的。

维护的是相邻两建筑顶(xi,hi)的连线的斜率的绝对值上升的单调栈。

从左往右一遍，右往左一遍。

下图是代码中judge函数的图，要判断是否建筑物被另一建筑物遮挡。

 #include <stdio.h>

 #include <string.h>

 #include <math.h>

 #include <iostream>

 #include <stack>

 #include <algorithm>

 #define PI acos(-1.0)

 using namespace std ;

 struct node

 {

     int pos ;

     int height ;

     bool operator <(const node &a)const

     {

         return pos < a.pos ;

     }

 } p[],stk[];

 double sh[] ;

 int T,n,q;

 int judge(node &a,node &b,node c){//判断在c处的视野中，a建筑物是否能够在c处没有被b建筑物挡住

     if(c.height <= ) c.height =  ;

     return (long long)(a.height-c.height)*(c.pos-b.pos) >= (long long)(b.height-c.height)*(c.pos-a.pos) ;

 }

 double angle(node a,node b)//求a建筑物与b处所成角的大小

 {

     return atan((double)(b.pos-a.pos)/(double)(a.height)) ;

 }

 void solve()

 {

     int top =  ;

     for(int i =  ; i < n+q ; i ++){

         if(p[i].height <= ){//是人的地方

             while(top >=  && judge(stk[top-],stk[top-],p[i])) top -- ;//如果top-1挡不住top-2的话，说明top-1在角度贡献上没什么用

             sh[-p[i].height] += angle(stk[top-],p[i]) ;

         }

         else

         {

             while(top && stk[top-].height <= p[i].height) top-- ;//如果栈顶元素没有新的这个高，那么肯定会被挡到，所以没有用删掉

             while(top >=  && judge(stk[top-],stk[top-],p[i])) top--;//把这三个建筑物的最高点相连，若是凹的，中间那个肯定会被挡到，删掉

             stk[top++] = p[i] ;

         }

     }

 }

 int main()

 {

     scanf("%d",&T) ;

     int casee =  ;

     while(T--)

     {

         scanf("%d",&n) ;

         for(int i =  ; i < n ; i++)

         {

             scanf("%d %d",&p[i].pos,&p[i].height) ;

         }

         scanf("%d",&q) ;

         for(int i =  ; i < q ; i++)

         {

             scanf("%d",&p[i+n].pos) ;

             p[i+n].height = -i ;//输出方便

         }

         memset(sh,,sizeof(sh)) ;

         sort(p,p+n+q) ;

         solve() ;

         reverse(p,p+n+q) ;

         for(int i =  ; i < n+q ; i++)//把后边的全部都移到前边去，与上边的统一，方便调用函数

             p[i].pos =  -p[i].pos ;

         solve() ;

         printf("Case #%d:\n",casee++) ;

         for(int i =  ; i < q ; i++){

             printf("%.10lf\n",sh[i]*/PI) ;//角度与弧度的转化

         }

     }

     return  ;

 }

巴特西

HDU 5033 Building (维护单调栈)

最新文章

热门文章