首页 > 代码库 > HDU 5033 Building（北京网络赛B题） 单调栈 找规律
HDU 5033 Building（北京网络赛B题） 单调栈 找规律
做了三天，，，终于a了。。。
| 11724203 | 2014-09-25 09:37:44 | Accepted | 5033 | 781MS | 7400K | 4751 B | G++ | czy |
Building
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 1257 Accepted Submission(s): 358 Special Judge
Problem Description
Once upon a time Matt went to a small town. The town was so small and narrow that he can regard the town as a pivot. There were some skyscrapers in the town, each located at position xi with its height hi. All skyscrapers located in different place. The skyscrapers had no width, to make it simple. As the skyscrapers were so high, Matt could hardly see the sky.Given the position Matt was at, he wanted to know how large the angle range was where he could see the sky. Assume that Matt‘s height is 0. It‘s guaranteed that for each query, there is at least one building on both Matt‘s left and right, and no building locate at his position.
Input
The first line of the input contains an integer T, denoting the number of testcases. Then T test cases follow.
Each test case begins with a number N(1<=N<=10^5), the number of buildings.
In the following N lines, each line contains two numbers, xi(1<=xi<=10^7) and hi(1<=hi<=10^7).
After that, there‘s a number Q(1<=Q<=10^5) for the number of queries.
In the following Q lines, each line contains one number qi, which is the position Matt was at.
Each test case begins with a number N(1<=N<=10^5), the number of buildings.
In the following N lines, each line contains two numbers, xi(1<=xi<=10^7) and hi(1<=hi<=10^7).
After that, there‘s a number Q(1<=Q<=10^5) for the number of queries.
In the following Q lines, each line contains one number qi, which is the position Matt was at.
Output
For each test case, first output one line "Case #x:", where x is the case number (starting from 1).
Then for each query, you should output the angle range Matt could see the sky in degrees. The relative error of the answer should be no more than 10^(-4).
Then for each query, you should output the angle range Matt could see the sky in degrees. The relative error of the answer should be no more than 10^(-4).
Sample Input
331 22 15 11431 32 25 11431 42 35 114
Sample Output
Case #1:101.3099324740Case #2:90.0000000000Case #3:78.6900675260
Source
2014 ACM/ICPC Asia Regional Beijing Online
Recommend
hujie | We have carefully selected several similar problems for you: 5041 5040 5039 5038 5036
题意及题解转自：http://www.cnblogs.com/yuiffy/p/3984776.html
题意：
城市看做二维平面，建筑看做x轴上某个位置为端点的竖着的线段，(xi,hi)表示在x轴xi位置有个高为hi的建筑（线段）。有多次询问，每次问人在某个平地上（x,0)能看到天空的角度。
题解：
维护 相邻两建筑顶(xi,hi)的连线的斜率的绝对值上升 的单调栈。
先把建筑和queries的点全部弄到一起，按xi排个序。然后从左到右来一波得出在某个空地往左看看到最高的是哪个建筑，再反过来来一波。
先按从左到右的情况来说：
维护单调栈，栈里存的是之后的空地可能看到的建筑，容易知这是递减的单调栈。
再思考，如果：
则只用存两边的点，中间那3个肯定看不到了。
如果：
则都要存，因为往右走的时候走着走着，右边第二个就比右边第一个高了，走着走着右边第三个又比右边第二个高了……（这时pop掉栈顶
可见我们存的是相邻两建筑顶(xi,hi)的连线的斜率的绝对值上升 的单调栈。
每看到一个空地，把栈首的不够高的都pop到，只留下那个能看到的最高的，然后把这个建筑加入结果记录中。（记录从这个空地往左看看到的最高的是哪个建筑）
反过来再来一遍。
最后再对询问搞一搞，就完啦。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<map> 9 #include<stack> 10 #include<string> 11 12 #define N 100005 13 #define M 10000002 14 #define mod 10000007 15 //#define p 10000007 16 #define mod2 100000000 17 //#define ll long long 18 //#define LL long long 19 #define maxi(a,b) (a)>(b)? (a) : (b) 20 #define mini(a,b) (a)<(b)? (a) : (b) 21 22 using namespace std; 23 24 int T; 25 int n; 26 int q; 27 const double pi=4*atan(1.0); 28 29 typedef struct 30 { 31 double x; 32 double h; 33 double xie; 34 double xier; 35 }BB; 36 37 BB b[N]; 38 39 typedef struct 40 { 41 double x; 42 double l; 43 double r; 44 double ans; 45 int num; 46 }QQ; 47 48 QQ Q[N]; 49 50 bool cmp1(BB c,BB d) 51 { 52 return c.x<d.x; 53 } 54 55 bool cmp2(QQ c,QQ d) 56 { 57 return c.x<d.x; 58 } 59 60 bool cmp3(QQ c,QQ d) 61 { 62 return c.num<d.num; 63 } 64 65 void ini() 66 { 67 int i; 68 scanf("%d",&n); 69 for(i=1;i<=n;i++){ 70 scanf("%lf%lf",&b[i].x,&b[i].h); 71 } 72 sort(b+1,b+1+n,cmp1); 73 scanf("%d",&q); 74 for(i=1;i<=q;i++){ 75 scanf("%lf",&Q[i].x); 76 Q[i].num=i; 77 } 78 sort(Q+1,Q+1+q,cmp2); 79 } 80 81 82 void solvel() 83 { 84 stack <BB> LL; 85 int i,j; 86 87 BB te; 88 double now; 89 b[1].xie=-1; 90 LL.push(b[1]); 91 j=2; 92 for(i=1;i<=q;i++){ 93 while(b[j].x<Q[i].x) 94 { 95 te=LL.top(); 96 while(LL.size()!=0 && b[j].h>te.h) 97 { 98 LL.pop(); 99 if(LL.size()==0) break;100 te=LL.top();101 }102 103 if(LL.size()==0){104 b[j].xie=-1;105 LL.push(b[j]);106 j++;107 continue;108 }109 110 now=(te.h-b[j].h)/(b[j].x-te.x);111 while(LL.size()>1 && now<te.xie){112 LL.pop();113 114 te=LL.top();115 now=(te.h-b[j].h)/(b[j].x-te.x);116 if(LL.size()<=1) break;117 }118 b[j].xie=now;119 LL.push(b[j]);120 j++;121 }122 123 te=LL.top();124 Q[i].l=te.h/(Q[i].x-te.x);125 LL.pop();126 if(LL.size()==0){127 LL.push(te);128 continue;129 }130 BB pre1=LL.top();131 double lte=pre1.h/(Q[i].x-pre1.x);132 while(LL.size()!=0 && lte>Q[i].l)133 {134 te=pre1;135 Q[i].l=lte;136 LL.pop();137 if(LL.size()==0){138 // LL.push(te);139 break;140 }141 pre1=LL.top();142 lte=pre1.h/(Q[i].x-pre1.x);143 }144 LL.push(te);145 }146 }147 148 149 void solver()150 {151 int i,j;152 stack<BB> RR;153 BB te;154 double now;155 b[n].xier=-1;156 RR.push(b[n]);157 j=n-1;158 for(i=q;i>=1;i--){159 while(b[j].x>Q[i].x)160 {161 te=RR.top();162 while(RR.size()!=0 && b[j].h>te.h)163 {164 RR.pop();165 if(RR.size()==0) break;166 te=RR.top();167 }168 169 if(RR.size()==0){170 b[j].xier=-1;171 RR.push(b[j]);172 j--;173 continue;174 }175 176 now=(te.h-b[j].h)/(-b[j].x+te.x);177 while(RR.size()>1 && now<te.xier){178 RR.pop();179 180 te=RR.top();181 now=(te.h-b[j].h)/(-b[j].x+te.x);182 if(RR.size()<=1) break;183 }184 b[j].xier=now;185 RR.push(b[j]);186 j--;187 }188 189 te=RR.top();190 Q[i].r=te.h/(-Q[i].x+te.x);191 RR.pop();192 if(RR.size()==0){193 RR.push(te);194 continue;195 }196 BB pre2=RR.top();197 double rte=pre2.h/(-Q[i].x+pre2.x);198 while(RR.size()!=0 && rte>Q[i].r)199 {200 te=pre2;201 Q[i].r=rte;202 RR.pop();203 if(RR.size()==0){204 // LL.push(te);205 break;206 }207 pre2=RR.top();208 rte=pre2.h/(-Q[i].x+pre2.x);209 }210 RR.push(te);211 }212 }213 214 void solve()215 {216 for(int i=1;i<=q;i++){217 Q[i].ans=(pi-atan(Q[i].l)-atan(Q[i].r))*180/pi;218 }219 }220 221 void out()222 {223 sort(Q+1,Q+1+q,cmp3);224 for(int i=1;i<=q;i++){225 printf("%.10f\n",Q[i].ans);226 }227 }228 229 int main()230 {231 //freopen("data.in","r",stdin);232 //freopen("data.out","w",stdout);233 scanf("%d",&T);234 for(int cnt=1;cnt<=T;cnt++)235 // while(T--)236 // while(scanf("%d%d",&n,&m)!=EOF)237 {238 // if(n==0 && m==0) break;239 printf("Case #%d:\n",cnt);240 ini();241 solvel();242 solver();243 solve();244 out();245 }246 247 return 0;248 }
HDU 5033 Building（北京网络赛B题） 单调栈 找规律
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。