HDU - 5033： Building（单调栈 ，求一排高楼中人看楼的最大仰角）

pro：现在在X轴上有N个摩天大楼，以及Q个人，人和大楼的坐标各不相同，保证每个人左边和右边都有楼，问每个人能看到天空的角度大小。

sol：不难想到就是维护凸包，此题就是让你模拟斜率优化，此处没有斜率来做，用几何写的。。。。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

const double pi=acos(-1.0);

struct in{

    double x,h; int id;

}s[maxn];

struct point{

    double x,y;

    point(){}

    point(double xx,double yy):x(xx),y(yy){}

};

double det(point a,point b){ return a.x*b.y-a.y*b.x;}

double dot(point a,point b){ return a.x*b.x+a.y*b.y;}

bool cmp(in w,in v){ return w.x<v.x;}

double ans[maxn];  int q[maxn],top;

void solve(int N)

{

    sort(s+,s+N+,cmp); top=;

    rep(i,,N){

        if(s[i].id){

            while(top>&&atan2(s[q[top]].h-s[q[top-]].h,s[q[top]].x-s[q[top-]].x)

                    <atan2(-s[q[top]].h,s[i].x-s[q[top]].x)) top--;

            point T=point(s[q[top]].h,s[q[top]].x-s[i].x);

            ans[s[i].id]+=asin(fabs(det(point(,-),T))/sqrt(dot(T,T)));

        }

        else {

            while(top&&s[q[top]].h<=s[i].h) top--;

            while(top>&&atan2(s[q[top]].h-s[q[top-]].h,s[q[top]].x-s[q[top-]].x)

                    <atan2(s[i].h-s[q[top]].h,s[i].x-s[q[top]].x)) top--;

            q[++top]=i;

        }

    }

}

int main()

{

    int T,N,Q,C=;

    scanf("%d",&T);

    while(T--){

        scanf("%d",&N);

        rep(i,,N){

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

            s[i].id=;

        }

        scanf("%d",&Q);

        rep(i,,Q){

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

            s[N+i].id=i,ans[i]=;  s[N+i].h=;

        }

        solve(N+Q);

        rep(i,,N+Q) s[i].x=-s[i].x;

        solve(N+Q);

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

        rep(i,,Q) printf("%.10lf\n",-/pi*ans[i]);

    }

    return ;

}