首页 > 代码库 > HDU 5033 Building (维护单调栈)
HDU 5033 Building (维护单调栈)
题目链接
题意:n个建筑物,Q条询问,问所在的位置,看到天空的角度是多少,每条询问的位置左右必定是有建筑物的。
思路 : 维护一个单调栈,将所有的建筑物和所有的人都放到一起开始算就行,每加入一个人,就维护栈里的建筑物的高度,也就是说这个人所能够看到的建筑物时在栈里的,但是这个人看不到的就删掉,例如下图,中间三个点可以删掉了,因为角度问题中间三个是看不到的,所以不会影响最终求得角度
还有一种情况,就是下述的情况,不停的维护单调栈,人站在不同的地方角度也是不一样的。
维护的是相邻两建筑顶(xi,hi)的连线的斜率的绝对值上升 的单调栈。
从左往右一遍,右往左一遍。
下图是代码中judge函数的图,要判断是否建筑物被另一建筑物遮挡。
1 #include <stdio.h> 2 #include <string.h> 3 #include <math.h> 4 #include <iostream> 5 #include <stack> 6 #include <algorithm> 7 #define PI acos(-1.0) 8 using namespace std ; 9 10 struct node11 {12 int pos ;13 int height ;14 bool operator <(const node &a)const15 {16 return pos < a.pos ;17 }18 } p[401210],stk[401210];19 double sh[401010] ;20 int T,n,q;21 22 23 int judge(node &a,node &b,node c){//判断在c处的视野中,a建筑物是否能够在c处没有被b建筑物挡住24 if(c.height <= 0) c.height = 0 ;25 return (long long)(a.height-c.height)*(c.pos-b.pos) >= (long long)(b.height-c.height)*(c.pos-a.pos) ;26 }27 28 double angle(node a,node b)//求a建筑物与b处所成角的大小29 {30 return atan((double)(b.pos-a.pos)/(double)(a.height)) ;31 }32 void solve()33 {34 int top = 0 ;35 for(int i = 0 ; i < n+q ; i ++){36 if(p[i].height <= 0){//是人的地方37 while(top >= 2 && judge(stk[top-2],stk[top-1],p[i])) top -- ;//如果top-1挡不住top-2的话,说明top-1在角度贡献上没什么用38 sh[-p[i].height] += angle(stk[top-1],p[i]) ;39 }40 else41 {42 while(top && stk[top-1].height <= p[i].height) top-- ;//如果栈顶元素没有新的这个高,那么肯定会被挡到,所以没有用删掉43 while(top >= 2 && judge(stk[top-2],stk[top-1],p[i])) top--;//把这三个建筑物的最高点相连,若是凹的,中间那个肯定会被挡到,删掉44 stk[top++] = p[i] ;45 }46 }47 }48 int main()49 {50 scanf("%d",&T) ;51 int casee = 1 ;52 while(T--)53 {54 scanf("%d",&n) ;55 for(int i = 0 ; i < n ; i++)56 {57 scanf("%d %d",&p[i].pos,&p[i].height) ;58 }59 scanf("%d",&q) ;60 for(int i = 0 ; i < q ; i++)61 {62 scanf("%d",&p[i+n].pos) ;63 p[i+n].height = -i ;//输出方便64 }65 memset(sh,0,sizeof(sh)) ;66 sort(p,p+n+q) ;67 solve() ;68 reverse(p,p+n+q) ;69 for(int i = 0 ; i < n+q ; i++)//把后边的全部都移到前边去,与上边的统一,方便调用函数70 p[i].pos = 10000000 -p[i].pos ;71 solve() ;72 printf("Case #%d:\n",casee++) ;73 for(int i = 0 ; i < q ; i++){74 printf("%.10lf\n",sh[i]*180/PI) ;//角度与弧度的转化75 }76 }77 return 0 ;78 }
HDU 5033 Building (维护单调栈)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。