题意：N 幢楼排成一列(1<=N<=10^5)，各楼有横坐标 xi(1<=xi<=10^7) 以及高度 hi(1<=hi<=10^7)，在各楼之间的Q个位置(1<=Q<=10^5)，问这些位置能够仰望天空的夹角是多少度。

题目链接：http://acm.hdu.edu.cn/showproblem.php?

pid=5033

——>>将楼和人的位置一起按 x 排序。。

从左往右扫，单调栈维护斜率小的。

。

从右往左扫。单调栈维护斜率大的。。

#include <cstdio>

#include <algorithm>

#include <cmath>

using std::sort;

const double EPS = 1e-8;

const double PI = acos(-1.0);

const int MAXN = 100000 + 10;

int N, Q, kase;

double L[MAXN], R[MAXN];

int Dcmp(double x)

{

    if (fabs(x) < EPS) return 0;

    return x > 0 ? 1 : -1;

}

struct BUILD

{

    double x;

    double h;

    int id;

    bool operator < (const BUILD& e) const

    {

        return Dcmp(x - e.x) < 0;

    }

} b[MAXN << 1];

double Slope(const BUILD& a, const BUILD& b)

{

    return (b.h - a.h) / (b.x - a.x);

}

int st[MAXN];

struct MS

{

    int top;

    MS(): top(0) {}

    void Push(int id)

    {

        st[top++] = id;

    }

    void PopMax(const BUILD* b, const int& id)

    {

        while (top >= 2 && Dcmp(Slope(b[id], b[st[top - 1]]) - Slope(b[id], b[st[top - 2]])) >= 0)

        {

            --top;

        }

    }

    void PopMin(const BUILD* b, const int& id)

    {

        while (top >= 2 && Dcmp(Slope(b[id], b[st[top - 1]]) - Slope(b[id], b[st[top - 2]])) <= 0)

        {

            --top;

        }

    }

    int Top()

    {

        return st[top - 1];

    }

};

void Read()

{

    scanf("%d", &N);

    for (int i = 1; i <= N; ++i)

    {

        scanf("%lf%lf", &b[i].x, &b[i].h);

        b[i].id = 0;

    }

    scanf("%d", &Q);

    for (int i = 1; i <= Q; ++i)

    {

        scanf("%lf", &b[i + N].x);

        b[i + N].id = i;

        b[i + N].h = 0.0;

    }

}

void Init()

{

    sort(b + 1, b + 1 + N + Q);

}

void GetLeft()

{

    MS ms;

    for (int i = 1; i <= N + Q; ++i)

    {

        if (!b[i].id)

        {

            ms.PopMax(b, i);

            ms.Push(i);

        }

        else

        {

            ms.PopMax(b, i);

            int j = ms.Top();

            L[b[i].id] = b[j].h / (b[i].x - b[j].x);

        }

    }

}

void GetRight()

{

    MS ms;

    for (int i = N + Q; i >= 1; --i)

    {

        if (!b[i].id)

        {

            ms.PopMin(b, i);

            ms.Push(i);

        }

        else

        {

            ms.PopMin(b, i);

            int j = ms.Top();

            R[b[i].id] = b[j].h / (b[j].x - b[i].x);

        }

    }

}

void Output()

{

    printf("Case #%d:\n", ++kase);

    for (int i = 1; i <= Q; ++i)

    {

        printf("%.10f\n", 180.0 / PI * (PI - atan(L[i]) - atan(R[i])));

    }

}

int main()

{

    int T;

    kase = 0;

    scanf("%d", &T);

    while (T--)

    {

        Read();

        Init();

        GetLeft();

        GetRight();

        Output();

    }

    return 0;

}