http://acm.hdu.edu.cn/showproblem.php?pid=5033

平面上有n个建筑，每个建筑由(xi,hi)表示，m组询问在某一个点能看到天空的视角范围大小。

维护一个凸包，据说可以用单调栈

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <iostream>

#include <algorithm>

using namespace std;

#define RD(x) scanf("%d",&x)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define clr0(x) memset(x,0,sizeof(x))

typedef long long LL;

const double pi = acos(-1.0);

const int INF = 2000000007;

map <double,int> hash;

struct node{

    double x,h;

}s[100005];

int n,ll[100005],rr[100005];

double ans;

set <double> st;

bool cmp(node a,node b)

{

    return a.x < b.x;

}

int main(){

    int _,q,cas = 1;

    RD(_);

    while(_--){

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

        RD(n);

        st.clear();

        hash.clear();

        for(int i = 1;i <= n;++i){

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

            ll[i] = rr[i] = i;

            st.insert(s[i].x);

        }

        sort(s+1,s+n+1,cmp);

        for(int i = 1;i <= n;++i){

            hash[s[i].x] = i;

            for(int j = i - 1;j >= 1;--j){

                if(s[j].h > s[i].h){

                    ll[i] = j;

                    break;

                }

                if(j == ll[j])  break;

            }

        }

        for(int i = n;i >= 1;--i){

            for(int j = i + 1;j <= n;++j){

                if(s[j].h > s[i].h){

                    rr[i] = j;

                    break;

                }

                if(j == rr[j])  break;

            }

        }

        RD(q);

        while(q--){

            double x;

            scanf("%lf",&x);

            int r = hash[*st.lower_bound(x)],l = r - 1;

            double bst = s[r].h/fabs(s[r].x - x);

            while(r != rr[r]){

                r = rr[r];

                if(s[r].h > bst*(s[r].x-x))

                    bst = s[r].h/(s[r].x-x);

            }

            ans = pi - atan(bst);

            bst = s[l].h/fabs(x - s[l].x);

            while(l != ll[l]){

                l = ll[l];

                if(s[l].h > bst*(x-s[l].x))

                    bst = s[l].h/(x-s[l].x);

            }

            ans -= atan(bst);

            printf("%.9lf\n",180.0*ans/pi);

        }

     }

     return 0;

 }