[hdu5033]单调队列

题意：x轴上有n棵树，询问你站在某个点的视角。从左至右，单调队列（类似凸包）维护下。我强迫症地写了个模板QAQ

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <map>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <ctime>
#include <cctype>
#include <set>

using namespace std;

#define mem0(a) memset(a, 0, sizeof(a))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define define_m int m = (l + r) >> 1
#define Rep(a, b) for(int a = 0; a < b; a++)
#define lowbit(x) ((x) & (-(x)))
#define constructInt4(name, a, b, c, d) name(int a = 0, int b = 0, int c = 0, int d = 0): a(a), b(b), c(c), d(d) {}
#define constructInt3(name, a, b, c) name(int a = 0, int b = 0, int c = 0): a(a), b(b), c(c) {}
#define constructInt2(name, a, b) name(int a = 0, int b = 0): a(a), b(b) {}

typedef double db;
typedef long long LL;
typedef pair<int, int> pii;
typedef multiset<int> msi;
typedef multiset<int>::iterator msii;
typedef set<int> si;
typedef set<int>::iterator sii;
typedef vector<int> vi;

const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[8] = {0, -1, 0, 1, -1, 1, 1, -1};
const int maxn = 1e5 + 7;
const int maxm = 1e5 + 7;
const int maxv = 1e7 + 7;
const int MD = 1e9 +7;
const int INF = 1e9 + 7;
const double PI = acos(-1.0);
const double eps = 1e-10;

struct Point {
    int x, y;
    bool operator < (const Point &opt) const {
        return x < opt.x || x == opt.x && y < opt.y;
    }
    double abs() {
        return sqrt((double)x * x + (double)y * y);
    }
    Point operator - (const Point &opt) const {
        return Point(x - opt.x, y - opt.y);
    }
    double operator * (const Point &opt) const {
        return (double)x * opt.x + (double)y * opt.y;
    }
    constructInt2(Point, x, y);
    void inp() {
        scanf("%d %d", &x, &y);
    }
    void outp() {
        printf("(%d, %d), ", x, y);
    }
};

bool cmp(const pii &a, const pii &b) {
    return a.first < b.first;
}

double Cross(const Point &a, const Point &b) {
    return (double)a.x * b.y - (double)a.y * b.x;
}

template<class T> struct MonotoneQueue{
    deque<T> Q;
    MonotoneQueue<T>() { Q.clear(); }
    T back() { return Q.back(); }
    T back2() { if (Q.size() < 2) return T(); return *(Q.end() - 2); }
    T front() { return Q.front(); }
    void clear() { Q.clear(); }
    bool empty() { return Q.empty(); }
    void add_back(T x) { while (!empty() && !(back() - back2() < x - back2())) Q.pop_back(); Q.push_back(x); }
    void pop_front() { Q.pop_front(); }
};

double toDegree(double x) { return x * 180.0 / PI; }

Point p[maxn], L[maxn], R[maxn];
pii qry[maxn];
int n, m;

struct Node {
    Point dot;
    bool operator < (const Node &a) const {
        return Cross(dot, a.dot) < eps;
    }
    Node operator - (const Node &opt) const {
        return Node(dot - opt.dot);
    }
    Node(Point dot = Point()): dot(dot) {}
};
MonotoneQueue<Node> DQ;

void work(Point a[]) {
    DQ.clear();
    DQ.add_back(p[0]);
    int now = 1;
    for (int i = 0; i < m; i++) {
        while (now < n && p[now].x < qry[i].first) {
            DQ.add_back(Node(p[now++]));
        }
        DQ.add_back(Node(Point(qry[i].first, 0)));
        a[qry[i].second] = (DQ.back2() - DQ.back()).dot;
    }
}

int main() {
    //freopen("in.txt", "r", stdin);
    int T, cas = 0;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            p[i].inp();
        }
        sort(p, p + n);
        cin >> m;
        for (int i = 0, x; i < m; i++) {
            scanf("%d", &x);
            qry[i] = make_pair(x, i);
        }
        sort(qry, qry + m, cmp);

        work(L);

        for (int i = 0; i < n; i++) {
            p[i].x = maxv - p[i].x;
        }
        sort(p, p + n);
        for (int i = 0; i < m; i++) {
            qry[i].first = maxv - qry[i].first;
        }
        sort(qry, qry + m, cmp);

        work(R);
        for (int i = 0; i < m; i++) {
            R[i].x = -R[i].x;
        }

        printf("Case #%d:
", ++cas);
        for (int i = 0; i < m; i++) {
            printf("%.10f
", toDegree(acos(L[i] * R[i] / L[i].abs() / R[i].abs())));
        }
    }
    return 0;
}