HDU 5033 Building

本文主要是介绍HDU 5033 Building，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

维护一个单调队列（用stack实现）

以左边为例，如果 2 位置 高度为 10 ，3 位置 高度为 2 ， 4 位置 高度为 5

则队列中存有 2、4 位置

然后每次计算人的时候计算整个队列里的情况

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <stack>
#include <algorithm>
#define maxn 100005
#define maxq 100005
#define PI acos(-1.0 )
#define eps (1e-10)using namespace std;struct Building
{double x;double h;double lAng;double rAng;
}building[maxn];struct Query
{int id;double pos;double lAng,rAng;
}query[maxq];
int t,cas,n,q;bool cmp1(Building a,Building b)
{return a.x+eps<b.x;
}bool cmp2(Query a,Query b)
{return a.pos+eps<b.pos;
}bool cmp3(Query a,Query b)
{return a.id<b.id;
}
stack <int> pre;int main()
{scanf("%d",&t);for(cas=1;cas<=t;cas++){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lf",&building[i].x);scanf("%lf",&building[i].h);}scanf("%d",&q);for(int i=1;i<=q;i++){scanf("%lf",&query[i].pos);query[i].id=i;}sort(building+1,building+1+n,cmp1);sort(query+1,query+1+q,cmp2);while(!pre.empty()) pre.pop();building[1].lAng=0.0;pre.push(1);int qIndex=1;while( qIndex<=q && query[qIndex].pos>building[1].x&& query[qIndex].pos<building[2].x ){double calAng;while(!pre.empty() && (calAng=(building[pre.top()].h)/fabs(query[qIndex].pos-building[pre.top()].x))<building[pre.top()].lAng )pre.pop();query[qIndex].lAng=calAng;qIndex++;}for(int i=2;i<=n;i++){double tmpAng;while(!pre.empty() && (tmpAng=((building[pre.top()].h-building[i].h) /fabs(building[i].x-building[pre.top()].x)) )<building[pre.top()].lAng)pre.pop();building[i].lAng=tmpAng;pre.push(i);while( qIndex<=q && query[qIndex].pos>building[i].x&& query[qIndex].pos<building[i+1].x ){double calAng;while(!pre.empty() && (calAng=(building[pre.top()].h)/fabs(query[qIndex].pos-building[pre.top()].x))<building[pre.top()].lAng )pre.pop();query[qIndex].lAng=calAng;qIndex++;}}while(!pre.empty()) pre.pop();building[n].rAng=0.0;pre.push(n);qIndex=q;while( qIndex>=1 && query[qIndex].pos<building[n].x && query[qIndex].pos>building[n-1].x ){double calAng;while(!pre.empty() && (calAng=(building[pre.top()].h)/fabs(building[pre.top()].x-query[qIndex].pos)) <building[pre.top()].rAng)pre.pop();query[qIndex].rAng=calAng;qIndex--;}for(int i=n-1;i>=1;i--){double tmpAng;while(!pre.empty() && (tmpAng=( (building[pre.top()].h-building[i].h)/fabs(building[pre.top()].x-building[i].x)))<building[pre.top()].rAng)pre.pop();building[i].rAng=tmpAng;pre.push(i);while( qIndex>=1 && query[qIndex].pos<building[i].x && query[qIndex].pos>building[i-1].x ){double calAng;while(!pre.empty() && (calAng=(building[pre.top()].h)/fabs(building[pre.top()].x-query[qIndex].pos)) <building[pre.top()].rAng)pre.pop();query[qIndex].rAng=calAng;qIndex--;}}
//for(int i=1;i<=n;i++)//   printf("%.10lf ",building[i].rAng/PI*180.0);
//printf("\n");sort(query+1,query+1+q,cmp3);printf("Case #%d:\n",cas);//cout<<q<<' ';for(int i=1;i<=q;i++){//printf("%.10lf %.10lf\n",query[i].lAng/PI*180.0,query[i].rAng/PI*180.0);printf("%.10lf\n",180.0-(atan(query[i].lAng)+atan(query[i].rAng))/PI*180.0 );}}return 0;
}
/*
10
2
1 0
3 0
1
2
Case #1:
180.0000000000
3
1 0 3 0
4 0.00000001
1
2
Case #2:
179.9999997135
3
5 1
1 4
2 3
1
4
Case #3:
78.6900675260
3
3
2 1
5 1
1 2
1
4
Case #4:
78.6900675260
180.0000000000
3
3
2 1
5 1
1 2
1
4
Case #5:
78.6900675260
180.0000000000*/

这篇关于HDU 5033 Building的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---