hdu 5033 模拟+单调优化

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:
",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
",180.0*ans/pi);
        }
     }
     return 0;
 }