BZOJ4049 [Cerc2014] Mountainous landscape

首先对于一个给定的图形，要找到是否存在答案非常简单。。。

只要维护当然图形的凸包，看一下是否有线段在这条直线上方，直接二分即可，单次询问的时间复杂度$O(logn)$

现在用线段树维护凸包，即对于一个区间$[l, r]$，我们维护点$[P_l, P_{r +1}]$形成的凸包

于是每次查询只要在线段树上二分，总复杂度$O(nlogn + nlog^2n)$(建树 + 查询)

 

/**************************************************************
    Problem: 4049
    User: rausen
    Language: C++
    Result: Accepted
    Time:5052 ms
    Memory:73960 kb
****************************************************************/
 
#include <cstdio>
#include <vector>
 
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
 
int read();
 
int n;
 
struct point {
    int x, y;
    point(int _x, int _y) : x(_x), y(_y) {}
    point() {}
     
    inline point operator + (const point &p) const {
        return point(x + p.x, y + p.y);
    }
    inline point operator - (const point &p) const {
        return point(x - p.x, y - p.y);
    }
    inline ll operator * (const point &p) const {
        return 1ll * x * p.y - 1ll * y * p.x;
    }
     
    inline void get() {
        x = read(), y = read();
    }
     
    friend inline ll calc(const point &a, const point &b, const point &c) {
        return (a - b) * (c - b);
    }
} p[N];
 
struct convex {
    vector <point> s;
     
    inline void clear() {
        s.clear();
    }
    #define top ((int) s.size() - 1)
    inline void insert(const point &p) {
        while (top > 0 && calc(p, s[top - 1], s[top]) <= 0) s.pop_back();
        s.push_back(p);
    }
     
    #define mid (l + r >> 1)
    inline bool query(const point &p, const point &q) {
        int l = 0, r = top - 1;
        while (l < r) {
            if (calc(s[mid], p, q) < calc(s[mid + 1], p, q)) r = mid;
            else l = mid + 1;
        }
        return calc(s[l], p, q) < 0 || calc(s[l + 1], p, q) < 0;
    }
    #undef mid
    #undef top
};
 
struct seg {
    seg *ls, *rs;
    convex c;
     
    #define Len (1 << 16)
    inline void* operator new(size_t, int f = 0) {
        static seg mempool[N << 2], *c;
        if (f) c = mempool;
        c -> ls = c -> rs = NULL, c -> c.clear();
        return c++;
    }
    #undef Len
     
    #define mid (l + r >> 1)
    void build(int l, int r) {
        int i;
        for (i = l; i <= r + 1; ++i) c.insert(p[i]);
        if (l == r) return;
        (ls = new()seg) -> build(l, mid);
        (rs = new()seg) -> build(mid + 1, r);
    }
     
    int query(int l, int r, int L, int R, const point &p, const point &q) {
        if (R < l || r < L) return 0;
        if (L <= l && r <= R) {
            if (!c.query(p, q)) return 0;
            if (l == r) return l;
        }
        int res = ls -> query(l, mid, L, R, p, q);
        return res ? res : rs -> query(mid + 1, r, L, R, p, q);
    }
    #undef mid
} *T;
 
int main() {
    int Tmp, i;
    for (Tmp = read(); Tmp; --Tmp) {
        n = read();
        for (i = 1; i <= n; ++i) p[i].get();
        (T = new(1)seg) -> build(1, n - 1);
        for (i = 1; i < n - 1; ++i)
            printf("%d ", T -> query(1, n - 1, i + 1, n - 1, p[i], p[i + 1]));
        puts("0");
    }
    return 0;
}
 
inline int read() {
    static int x;
    static char ch;
    x = 0, ch = getchar();
    while (ch < '0' || '9' < ch)
        ch = getchar();
    while ('0' <= ch && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}