hdu 5033 Building(单调性+二分)

题目链接：hdu 5033 Building

题目大意：城市里有n座摩天大厦，给定每栋大厦的位置和高度，假定大厦的宽度为0。现在有q次查询，表示人站的位置，人的高度视为0，问说可以仰望天空的角度。

解题思路：比赛的时候用单调性优化直接给过了，对于每个大厦来说，记录左右两边与其形成斜率最大的大厦序号以及斜率，然后每次查询是，通过二分确认人所在位置属于哪两栋大厦之间，然后分别向左向右确认角度，在确认角度时，根据大厦记录的最大斜率进行判断。
以左边为例，

然后对于查询位置x：

这种解法仅仅是优化查询效率而已，对于极端数据（斜率一直处于递减），对于单次查询复杂度就变成了o(n)，虽然测试样例没有这样的数据，但貌似不是正解。

C++  优化查询
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

const int maxn = 2 * 1e5 + 5;
const double pi = atan(1.0) * 4;

struct point {
    double x, h;
    bool operator < (const point& u) const {
        return x < u.x;
    }
}p[maxn];

struct edge {
    int v;
    double k;

    void set (int v, double k) {
        this->v = v;
        this->k = k;
    }
}l[maxn], r[maxn];

int N;

inline double get_k(const point& a, const point& b) {
    return (a.h - b.h) / fabs(b.x - a.x);
}

void init () {
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        scanf("%lf%lf\n", &p[i].x, &p[i].h);
    sort(p, p + N);

    l[0].set(-1, 0);
    for (int i = 1; i < N; i++) {
        int u = i - 1;

        while (l[u].v != -1 && l[u].k > get_k(p[u], p[i]))
            u = l[u].v;

        l[i].v = u;
        l[i].k = get_k(p[u], p[i]);
    }

    r[N-1].set(-1, 0);
    for (int i = N - 2; i >= 0; i--) {
        int u = i + 1;

        while (r[u].v != -1 && r[u].k > get_k(p[u], p[i]))
            u = r[u].v;

        r[i].v = u;
        r[i].k = get_k(p[u], p[i]);
    }
}

void solve () {
    int n;
    point q;
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%lf", &q.x);
        q.h = 0;
        int idx = lower_bound(p, p + N, q) - p;

        int mv = idx - 1;
        while (l[mv].v != -1 && l[mv].k > get_k(p[mv], q))
            mv = l[mv].v;

        while (r[idx].v != -1 && r[idx].k > get_k(p[idx], q))
            idx = r[idx].v;
        double R = pi - atan(get_k(p[mv], q)) + atan(get_k(q, p[idx]));
        printf("%.10lf\n", R / pi * 180);
    }
}

int main () {
    int cas;
    scanf("%d", &cas);
    for (int kcas = 1; kcas <= cas; kcas++) {
        init();
        printf("Case #%d:\n", kcas);
        solve();
    }
    return 0;
}

赛后和队友讨论了一下，觉得用离线算法应该是正解，将所有查询预先度入，然后统一按照x坐标排序，同样是以左边为例，维护斜率的单调栈，然后碰到询问点就直接在栈中二分，这样单次查询的复杂度就变成了o(logn)。

当处理到x2时，栈中存在<2>号边；当处理到x1询问时，栈中存在<3>,<4>,<5>号边，每次根据询问坐标对栈中的边进行二分。

C++ 二分
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn = 2 * 1e5 + 5;
const double pi = atan(1.0) * 4;

struct point {
    int idx;
    double x, h;
    point (int idx = 0, double x = 0, double h = 0) {
        this->idx = idx;;
        this->x = x;
        this->h = h;
    }

    bool operator < (const point& u) const {
        return x < u.x;
    }
};

struct edge {
    int v;
    double k;

    edge (int v, double k) {
        this->v = v;
        this->k = k;
    }
};

int N;
double l[maxn], r[maxn];
vector<point> p;
vector<edge> g;

inline double get_k(const point& a, const point& b) {
    return (a.h - b.h) / fabs(b.x - a.x);
}

void init () {

    p.clear();

    double x, h;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%lf%lf", &x, &h);
        p.push_back(point(0, x, h));
    }

    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%lf", &x);
        p.push_back(point(i, x, 0));
    }
    sort(p.begin(), p.end());
}

double bsearch (point u) {
    int L = 0, R = g.size();

    while (L < R) {
        int mid = (L + R) / 2;
        if (g[mid].k > get_k(p[g[mid].v], u))
            R = mid;
        else
            L = mid + 1;
    }

    L--;
    double k = p[g[L].v].h / fabs(p[g[L].v].x - u.x);
    return  atan(k);
}

void solve () {

    g.clear();
    g.push_back(edge(0, -1));
    for (int i = 1; i < p.size(); i++) {
        if (p[i].idx > 0) {
            l[p[i].idx] = bsearch(p[i]);
        } else {

            int u = g.size() - 1;
            while (u && g[u].k > get_k(p[g[u].v], p[i])) {
                g.pop_back();
                u--;
            }
            g.push_back(edge(i, get_k(p[g[u].v], p[i])));
        }
    }

    g.clear();
    g.push_back(edge(p.size()-1, -1));
    int u = p.size() - 1;
    for (int i = p.size() - 2; i >= 0; i--) {
        if (p[i].idx > 0) {
            r[p[i].idx] = bsearch(p[i]);
        } else {

            int u = g.size() - 1;
            while (u && g[u].k > get_k(p[g[u].v], p[i])) {
                g.pop_back();
                u--;
            }

            g.push_back(edge(i, get_k(p[g[u].v], p[i])));
        }
    }

    for (int i = 1; i <= N; i++)
        printf("%.10lf\n", (pi - l[i] - r[i]) / pi * 180);
}

int main () {
    int cas;
    scanf("%d", &cas);
    for (int kcas = 1; kcas <= cas; kcas++) {
        init();
        printf("Case #%d:\n", kcas);
        solve();
    }
    return 0;
}