首页 > 代码库 > HDU 5033 Building
HDU 5033 Building
题意:
地面上有n座楼 你分别站在m个位置上 问每个位置上能看见多大角度的天空
思路:
很明显能想到在站的位置两边维持单调性 因此我们可以将站位和楼的位置排序 从左到右维护一遍 再从右到左维护一遍 这里可以利用单调栈 对于新扫描到的位置 如果是楼 那么栈中比它矮的楼就没用了可以出栈 如果是站位 可以这样判断 如果可以看见栈底的楼(最高的楼)那么前面的矮楼一定不会影响后面了 可以出栈
代码:
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<cassert> #include<vector> #include<set> #include<map> #include<queue> using namespace std; #define N 100010 #define PI acos(-1) struct node { int id; double x, h; bool operator<(const node ff) const { return x < ff.x; } } nd[N * 2], st[N]; double ansl[N], ansr[N]; int n, m, t, T, tot, top; int main() { int i, j, id; double fh, fx, dx, k; scanf("%d", &T); for (t = 1; t <= T; t++) { tot = 0; scanf("%d", &n); for (i = 1; i <= n; i++) { scanf("%lf%lf", &fx, &fh); nd[tot].id = 0; nd[tot].x = fx; nd[tot].h = fh; tot++; } scanf("%d", &m); for (i = 1; i <= m; i++) { scanf("%lf", &fx); nd[tot].id = i; nd[tot].x = fx; tot++; ansl[i] = ansr[i] = 0; } sort(nd, nd + tot); //L top = 0; for (i = 0; i < tot; i++) { if (nd[i].id) { id = nd[i].id; dx = nd[i].x; fh = st[0].h; fx = st[0].x; while (top > 1 && fh / (dx - fx) >= st[top - 1].h / (dx - st[top - 1].x)) top--; for (j = 0; j < top; j++) { k = st[j].h / (dx - st[j].x); if (ansl[id] < k) ansl[id] = k; } } else { while (top && nd[i].h >= st[top - 1].h) top--; st[top++] = nd[i]; } } //R top = 0; for (i = tot - 1; i >= 0; i--) { if (nd[i].id) { id = nd[i].id; dx = nd[i].x; fh = st[0].h; fx = st[0].x; while (top > 1 && fh / (fx - dx) >= st[top - 1].h / (st[top - 1].x - dx)) top--; for (j = 0; j < top; j++) { k = st[j].h / (st[j].x - dx); if (ansr[id] < k) ansr[id] = k; } } else { while (top && nd[i].h >= st[top - 1].h) top--; st[top++] = nd[i]; } } printf("Case #%d:\n", t); for (i = 1; i <= m; i++) { printf("%f\n", 180.0 - (atan(ansl[i]) + atan(ansr[i])) / PI * 180); } } return 0; }
HDU 5033 Building
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。