本来以为是一道简单题谁知道结果一直超时所以不得不上网搜了一下思路，原来使用的是单调栈。
单调栈的主要特点表现为不断进栈出栈使栈内元素保持一定的单调性，在查找最大值或者最小值时对时间的减小用很大的作用。
题意：N 幢楼排成一列(1<=N<=10^5)，各楼有横坐标 xi(1<=xi<=10^7) 以及高度 hi(1<=hi<=107)，在各楼之间的Q个位置(1<=Q<=105)，问这些位置可以仰望天空的夹角是多少度。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5033
——>>将楼和人的位置一起按 x 排序。。
从左往右扫，单调栈维护斜率小的。。
从右往左扫，单调栈维护斜率大的。。
题意分析：
这些楼房的位置和人的坐标都可以按照从左到右的坐标排序，从而在结构体数组得到如上图所示的结果。
既然求的是最大的天空度数，那么应该保留到达位置差与高度差的最大比，该比即为最大角度的正切值。
可以根据单调栈的维护来进行数据处理。
A1
A2
如图：首先将两个元素进栈，然后从第三个开始，判断角度，如果前面的小于后面的，则不用出栈，因为栈顶元素总为较大的，否则，后面的元素出栈，出栈后，栈顶元素即仍为较大的角度，最后将当前元素入栈，便于下次判断。上图所示：第一附图经比较2》1，那么只进栈3，若第二幅图的情况，则需要出栈2，再进栈3。
依次类推判断，直到遇到了人的位置，那么就需要将人的位置作为当前位置，与栈顶的元素进行正切值的对比，较大的正切值则作为左边的答案存放在答案数组中。
由此推断可以得出，在栈内存放的数据形态应该如下所示：
图1
假设这是栈的原始状态，那么想要向后遍历原始数组，那么下一个楼房会出现两种状态，
一、比当前的楼房矮。
二、比当前楼房高，这种情况又会出现上述的两种是否需要维护栈的问题。
具体图示：
而当有一个比栈顶的元素高的楼房出现，则会有：
情况一
而后一直出栈，直到也获得最大的夹角出现，便为新的栈内数据状态：
在图一时，若遇到第一种状况，那么只需要将当前元素进栈即可：
情况二
当遇到第二种状况时，照例出栈
情况三
出栈后仍需继续判断与栈顶的角度关系，并确定是否仍旧需要继续出栈：
如图所示情况，不需出栈。
当遇到人所站的位置之后，需首先判断最大角，然后将该最大角加入自己的答案数组，当做一边的角，由于人的高度为零，任何情况下都会有楼房比零高，所以可以选择不入栈。
另一边的角则需要利用reverse函数将原始数组反转，再从左向右判断，直到找到所有的人的位置所在的右边的角，并加入答案数组，依次输出答案数组，此题AC。
然后便是简单的代码解读:
首先必须要写的函数是角度的比较问题，即三个点，两个栈内，一个栈外，根据角度判断栈顶是否需要出栈，那么需要把栈顶和栈顶下面的元素进行比较，公式为：假设栈顶为b，前一个为a，预进栈的元素为c。
根据A1A2，判断是否：
（a.x-c.x）/（a.h-c.h）>=（b.x-c.x）/（b.h-c.h）。整理得：
(a.h - c.h) (c.x - b.x) >= (ll)(b.h - c.h) * (c.x - a.x)。
故有：
int check(Node a, Node b, Node c)
{
return (ll)(a.h - c.h) * (c.x - b.x) >= (ll)(b.h - c.h) * (c.x - a.x);
}
然后进行维护栈函数的构造：
若当前预进栈元素是人的坐标，则一定是比前面的元素低的，故只需判断是否需出栈元素即可，调用check函数判断，若不用，直接将最大角放入答案数组，否则，不断判断是否需出栈，直到不需出栈，即找到了当前的最大角度，再加入答案数组。
if (node[i].h <= 0)
{
while (head >= 2 && check(stk[head - 2], stk[head - 1], node[i]))
head--;
ans[i] += ang(stk[head - 1], node[i]);
}
ang函数表示把角度计算出来的构造函数。
如果不是人的坐标，那么需判断是否高于栈顶，如果是，则出栈，直到不再高于 ，然后进行低于栈顶情况的判断和运算。
while (head && stk[head - 1].h <= node[i].h)
head--;
否则，判断是否出栈，是则不断出，否则将当前元素入栈：
while (head >= 2 && check(stk[head - 2], stk[head - 1], node[i]))
head--;
stk[head++] = node[i];
有了这几个判断这道题便非常明了了，下面的代码便也可以轻易明白了：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
typedef long long ll;
using namespace std;
const double PI = acos(-1.0);
const int maxn = 200100;
const int inf = 1e8;
struct Node
{
int x, h;
bool operator <(const Node &a)const
{
return x < a.x;
}
} node[maxn], stk[maxn];
double ans[maxn];
int n, q;
int check(Node a, Node b, Node c)
{
if (c.h <= 0)
c.h = 0;
return (ll)(a.h - c.h) * (c.x - b.x) >= (ll)(b.h - c.h) * (c.x - a.x);
}
double ang(Node a, Node b)
{
return atan(1.0 * (b.x - a.x) / a.h);
}
void solve()
{
int head = 0;
for (int i = 0; i < n + q; i++)
{
if (node[i].h <= 0)
{
while (head >= 2 && check(stk[head - 2], stk[head - 1], node[i]))
head--;
ans[-node[i].h] += ang(stk[head - 1], node[i]);
}
else
{
while (head && stk[head - 1].h <= node[i].h)
head--;
while (head >= 2 && check(stk[head - 2], stk[head - 1], node[i]))
head--;
stk[head++] = node[i];
}
}
}
int main()
{
int t, cas = 1;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d%d", &node[i].x, &node[i].h);
scanf("%d", &q);
for (int i = 0; i < q; i++)
{
scanf("%d", &node[i + n].x);
node[i + n].h = -i;
}
memset(ans, 0, sizeof(ans));
sort(node, node + n + q);
solve();
reverse(node, node + n + q);
for (int i = 0; i < n + q; i++)
node[i].x = inf - node[i].x;
solve();
printf("Case #%d:\n", cas++);
for (int i = 0; i < q; i++)
printf("%.10lf\n", ans[i] * 180.0 / PI);
}
return 0;
}
网友评论