本來以為是一道簡單題誰知道結(jié)果一直超時所以不得不上網(wǎng)搜了一下思路，原來使用的是單調(diào)棧蕴侧。
單調(diào)棧的主要特點表現(xiàn)為不斷進棧出棧使棧內(nèi)元素保持一定的單調(diào)性，在查找最大值或者最小值時對時間的減小用很大的作用。
題意：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 排序沪曙。。
從左往右掃萎羔，單調(diào)棧維護斜率小的液走。。
從右往左掃，單調(diào)棧維護斜率大的缘眶。嘱根。
題意分析：
這些樓房的位置和人的坐標都可以按照從左到右的坐標排序巷懈，從而在結(jié)構(gòu)體數(shù)組得到如上圖所示的結(jié)果该抒。
既然求的是最大的天空度數(shù)，那么應該保留到達位置差與高度差的最大比顶燕，該比即為最大角度的正切值凑保。
可以根據(jù)單調(diào)棧的維護來進行數(shù)據(jù)處理。
如圖：首先將兩個元素進棧涌攻，然后從第三個開始欧引，判斷角度，如果前面的小于后面的癣漆，則不用出棧维咸，因為棧頂元素總為較大的，否則惠爽，后面的元素出棧癌蓖，出棧后，棧頂元素即仍為較大的角度婚肆，最后將當前元素入棧租副，便于下次判斷。上圖所示：第一附圖經(jīng)比較2》1较性，那么只進棧3用僧，若第二幅圖的情況，則需要出棧2赞咙，再進棧3责循。
依次類推判斷，直到遇到了人的位置攀操，那么就需要將人的位置作為當前位置院仿，與棧頂?shù)脑剡M行正切值的對比，較大的正切值則作為左邊的答案存放在答案數(shù)組中速和。
由此推斷可以得出歹垫，在棧內(nèi)存放的數(shù)據(jù)形態(tài)應該如下所示：
假設(shè)這是棧的原始狀態(tài)，那么想要向后遍歷原始數(shù)組颠放，那么下一個樓房會出現(xiàn)兩種狀態(tài)排惨，
一、比當前的樓房矮碰凶。
二暮芭、比當前樓房高鹿驼，這種情況又會出現(xiàn)上述的兩種是否需要維護棧的問題。
具體圖示：
而當有一個比棧頂?shù)脑馗叩臉欠砍霈F(xiàn)谴麦，則會有：
而后一直出棧蠢沿，直到也獲得最大的夾角出現(xiàn)，便為新的棧內(nèi)數(shù)據(jù)狀態(tài)：
在圖一時匾效，若遇到第一種狀況舷蟀，那么只需要將當前元素進棧即可：
出棧后仍需繼續(xù)判斷與棧頂?shù)慕嵌汝P(guān)系面哼，并確定是否仍舊需要繼續(xù)出棧：
如圖所示情況野宜，不需出棧。
當遇到人所站的位置之后魔策，需首先判斷最大角匈子，然后將該最大角加入自己的答案數(shù)組，當做一邊的角闯袒，由于人的高度為零虎敦，任何情況下都會有樓房比零高，所以可以選擇不入棧政敢。
另一邊的角則需要利用reverse函數(shù)將原始數(shù)組反轉(zhuǎn)其徙，再從左向右判斷，直到找到所有的人的位置所在的右邊的角喷户，并加入答案數(shù)組唾那，依次輸出答案數(shù)組，此題AC褪尝。
然后便是簡單的代碼解讀:
首先必須要寫的函數(shù)是角度的比較問題闹获，即三個點，兩個棧內(nèi)河哑，一個棧外避诽，根據(jù)角度判斷棧頂是否需要出棧，那么需要把棧頂和棧頂下面的元素進行比較璃谨，公式為：假設(shè)棧頂為b茎用，前一個為a，預進棧的元素為c睬罗。
根據(jù)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);
}
然后進行維護棧函數(shù)的構(gòu)造：
若當前預進棧元素是人的坐標，則一定是比前面的元素低的垂券，故只需判斷是否需出棧元素即可花盐，調(diào)用check函數(shù)判斷羡滑，若不用，直接將最大角放入答案數(shù)組算芯，否則柒昏，不斷判斷是否需出棧，直到不需出棧熙揍，即找到了當前的最大角度职祷，再加入答案數(shù)組。
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函數(shù)表示把角度計算出來的構(gòu)造函數(shù)届囚。
如果不是人的坐標有梆，那么需判斷是否高于棧頂，如果是意系，則出棧泥耀，直到不再高于 ，然后進行低于棧頂情況的判斷和運算蛔添。
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;
}
