HDU 5033 Building （单调栈、计算几何）

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=5033

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

参考博客：http://www.cnblogs.com/luyingfeng/p/4015378.html

很厉害，有很多巧妙地思维我没想到。。。佩服

把所有点放在一起，然后从头看，是建筑物就入栈，但入栈时要保证把对角度不产生影响的建筑物丢弃，也就相当于是求一个凸包把。正着搞一遍，反着再搞一遍。思想很简单，但是实现起来还是有很多细节需要考虑的，都标注在注释了。

#include <bits/stdc++.h>
#define PI acos(-1.0)
using namespace std;
int n, q;
struct node{
int pos, hei;
};
node in[200010], Stack[200010];
double ans[200010];
bool cmp(node a, node b) {
return a.pos < b.pos;
}
bool check(node a, node b, node c) { //叉乘判断是否需要删掉
if(c.hei < 0) c.hei = 0;
int cax = a.pos - c.pos, cay = a.hei - c.hei;
int cbx = b.pos - c.pos, cby = b.hei - c.hei;
if((long long)cax * cby - (long long)cay * cbx >= 0) return 1;
return 0;
}
double angle(node a, node b) {
return atan((double)(b.pos - a.pos) / (double)a.hei);
}
void solve() {
int top = 0;
for(int i = 1; i <= n + q; i++)
{
if(in[i].hei > 0) {
while(top && Stack[top - 1].hei <= in[i].hei) top--;
//保证栈的单调
while(top >= 2 && check(Stack[top - 2], Stack[top - 1], in[i])) top--; //凸包
Stack[top++] = in[i];
}
else { //诗人
while(top >= 2 && check(Stack[top - 2], Stack[top - 1], in[i])) top--;
ans[-in[i].hei] += angle(Stack[top - 1], in[i]);
//两个角度相加
}
}
}
int main() {
int t;
scanf("%d", &t);
for(int kase = 1; kase <= t; kase++) {
printf("Case #%d:n", kase);
memset(ans, 0, sizeof ans);
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d %d", &in[i].pos, &in[i].hei);
}
scanf("%d", &q);
for(int i = 1; i <= q; i++) {
scanf("%d", &in[n + i].pos);
in[n + i].hei = -i;
//如此标记方便输出
}
sort(in + 1, in + n + q + 1, cmp);
solve();
reverse(in + 1, in + n + q + 1);
//反转用原来的函数再求一边
for(int i = 1; i <= n + q + 1; i++) { //这里要注意坐标也要改变，但是坐标间的距离不能改变，所以这样一减就可以实现了
in[i].pos = 100000 - in[i].pos;
}
solve();
for(int i = 1; i <= q; i++) {
printf("%.10lfn", ans[i] * 180 / PI);
}
}
return 0;
}

最后

以上就是留胡子歌曲为你收集整理的HDU 5033 Building （单调栈、计算几何）的全部内容，希望文章能够帮你解决HDU 5033 Building （单调栈、计算几何）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。