hdu 5033 Building 單調棧

第一次寫的單調棧。

本題參考http://www.cnblogs.com/yuiffy/p/3984776.html

題意：

在水準的軸上，有着多個建築物，建築物寬度可以看做為0，高度為hi，讓你求出在所給的點，所能仰望的最大角度。

AC代碼：

（代碼長度應該可以優化一下）

/* **********************************************
Created Time: 2014-9-24 13:32:33
File Name   : hdu5033.cpp
*********************************************** */
//#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <fstream>
#include <cstring>
#include <climits>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <functional>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e5+5;
const double PI = acos(-1.0);
struct Point
{
        double x, h;
        double k, res;
        int rank;
}bq[2*MAXN];
int n, q;
double recl[MAXN], recr[MAXN];          //record k;
bool cmp(Point a, Point b)
{
        return a.x < b.x;
}
bool cmp2(Point a, Point b)
{
        return a.rank < b.rank;
}
void solve()
{
        sort(bq, bq+n+q, cmp);
        int nq = n+q;
        //left to right, find the left max view;
        stack <Point> sta;
        int cot = 0;
        for(int i = 0;i < nq; i++)
        {
                if(bq[i].h != 0)        //building
                {
                        //check high
                        while(!sta.empty())
                        {
                                if(sta.top().h <= bq[i].h)      sta.pop();
                                else    break;
                        }
                        //
                        if(sta.size() == 1)
                        {
                                Point &e = sta.top();
                                bq[i].k = (e.h - bq[i].h)/(e.x - bq[i].x);
                                sta.push(bq[i]);
                        }
                        else if(sta.size() == 0)
                        {
                                bq[i].k = 0;
                                sta.push(bq[i]);
                        }
                        else
                        {
                                double curk;
                                while(!sta.empty())
                                {
                                        Point &e = sta.top();
                                        curk = (e.h-bq[i].h)/(e.x-bq[i].x);
                                        if(curk >= e.k)
                                                sta.pop();
                                        else
                                                break;
                                }
                                bq[i].k = curk;
                                sta.push(bq[i]);

                        }
                }
                else                    //Query
                {
                        double curk;
                        while(!sta.empty())
                        {
                                Point &e = sta.top();
                                curk = (e.h-bq[i].h)/(e.x-bq[i].x);
                                if(curk <= e.k)
                                        break;
                                else
                                        sta.pop();
                        }
                        recl[cot++] = curk;
                }
        }
        //right to left, find the right max view;
        int cot2 = cot-1;
        while(!sta.empty())     sta.pop();
        for(int i = nq-1; i >= 0; i--)
        {
                if(bq[i].h != 0)
                {
                        while(!sta.empty())
                        {
                                if(bq[i].h >= sta.top().h)       sta.pop();
                                else            break;
                        }
                        if(sta.size() == 1)
                        {
                                Point &e = sta.top();
                                bq[i].k = (e.h-bq[i].h)/(e.x-bq[i].x);
                                sta.push(bq[i]);
                        }
                        else if(sta.size() == 0)
                        {
                                bq[i].k = 0;
                                sta.push(bq[i]);
                        }
                        else
                        {
                                double curk;
                                while(!sta.empty())
                                {
                                        Point &e = sta.top();
                                        curk = (e.h-bq[i].h)/(e.x-bq[i].x);
                                        if(curk <= e.k)
                                                sta.pop();
                                        else
                                                break;
                                }
                                bq[i].k = curk;
                                sta.push(bq[i]);
                        }
                }
                else
                {
                        double curk;
                        while(!sta.empty())
                        {
                                Point &e = sta.top();
                                curk = (e.h-bq[i].h)/(e.x-bq[i].x);
                                if(curk > e.k)
                                        break;
                                else
                                        sta.pop();
                        }
                        recr[cot2--] = curk;
                }
        }
}

int main()
{
        int T, cas = 0;
        scanf("%d", &T);
        while(T--)
        {
                //input
                scanf("%d", &n);
                for(int i = 0;i < n; i++)
                {
                        scanf("%lf%lf", &bq[i].x, &bq[i].h);
                        bq[i].rank = i;
                }

                scanf("%d", &q);
                for(int i = n;i < q+n; i++)
                {
                        scanf("%lf", &bq[i].x);
                        bq[i].h = 0, bq[i].rank = i;
                }
                //
                //
                solve();
                int cot = 0;
                for(int i = 0;i < q+n; i++)
                {
                        if(bq[i].h != 0)        continue;
                        bq[i].res = 180 - atan(abs(recl[cot]))*180/PI - atan(recr[cot])*180/PI;
                        cot++;
                }
                sort(bq, bq+n+q, cmp2);
                printf("Case #%d:\n", ++cas);
                for(int i = n;i < q+n; i++)
                        printf("%.5lf\n", bq[i].res);
        }
        return 0;
}