50分求助

#include <bits/stdc++.h>
#define fi first
#define se second
#define mk make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define VT vector
#define pb push_back
#define SZ(a) ((int)a.size())
#define all(a) a.begin(), a.end()
#define TP template <class o>
#define TPP template <typename t1, typename t2>
#define rep(i, a, b) for (int i = a, i##ed_ = b; i <= i##ed_; i++)
#define REP(i, a, b) for (int i = b, i##st_ = a; i >= i##st_; i--)
#define FOR(i, n) rep(i, 1, n)
#define debug(x)
using namespace std;
typedef double db;
typedef unsigned ui;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef unsigned long long ull;

// char buf[1 << 20],*p1=buf,*p2=buf;
#define gc getchar() //(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
TP void qr(o& x) {
    char c = gc; x = 0; int f = 1; 
    while (!isdigit(c)) {if (c == '-') f = -1; c = gc;}
    while (isdigit(c)) x = x * 10 + c - '0', c = gc;
    x *= f;
}
template <class o, class... O> void qr(o& x, O&... y) { qr(x), qr(y...); }
TP void qw(o x) {
    if (x < 0) putchar('-'), x = -x;
    if (x / 10) qw(x / 10);     
    putchar(x % 10 + '0');
}
TP void pr1(o x) { qw(x), putchar(' '); }
template <class o, class... O> void pr1(o x, O... y) { pr1(x), pr1(y...); }
TP void pr2(o x) { qw(x), putchar(10); }
template <class o, class... O> void pr2(o x, O... y) { pr2(x), pr2(y...); }

const int N = 2e5 + 10;
const db eps = 1e-6, inf = 1e18, PI = acos(-1.0); //精度
int sign(db x) {return x < -eps ? -1: (x > eps ? 1: 0);} // 符号位
    
struct P {
    db x, y;
    P(db x = 0, db y = 0):x(x), y(y){}
    P operator +(P b) const {return P(x + b.x, y + b.y);}
    P operator -(P b) const {return P(x - b.x, y - b.y);}
    db operator *(P b) const {return x * b.y - y * b.x;}
    db slope() const {return y / x;}
    db angle() {return atan2(y, x);}
} p[N];

int n, m, q;

struct Edge {
    int u, v, w;
    db angle;
    Edge(){}
    Edge(int u, int v, int w):u(u), v(v), w(w) {
        angle = (p[v] - p[u]).angle();
    }
} e[N]; int len, rk[N], near[N], num;
bool inf_id[N];
VT<int> g[N];

namespace RD { // regional division
    void dfs(int x, int k) {
        if(near[k]) return;
        num++;
        db S = 0;
        while(!near[k]) {
            S += p[x] * p[e[k].v];
            near[k] = num;
            x = e[k].v; 
            k ^= 1;
            if(!rk[k]) k = g[x].back();
            else k = g[x][rk[k] - 1];
        }
        inf_id[num] = S < 0; // 最外层无界区域为1
    }
    void solve() {
        int x, y, z; len = 0;
        FOR(i, m) {
            qr(x, y, z);
            e[len++] = Edge(x, y, z);
            e[len++] = Edge(y, x, z);
        }
        VT<int> id(len); iota(all(id), 0);
        sort(all(id), [&](int a, int b) {return e[a].angle < e[b].angle;});
        for(int k: id) {
            rk[k] = g[x = e[k].u].size();
            g[x].push_back(k);
        }
        // for(int j: id) dfs(e[j].u, j);
        FOR(i, n) for(int j: g[i]) dfs(i, j);
    }
}

namespace MST { // Kruskal
    int F[N][20], fa[N], lg, val[N], dep[N], son[N][2];
    int get(int x) {return fa[x] == x ? x : fa[x] = get(fa[x]);}
    void dfs(int x) {
        rep(i, 0, 1) {
            int y = son[x][i];
            if(y) {
                dep[y] = dep[x] + 1;
                F[y][0] = x;
                FOR(i, lg) F[y][i] = F[F[y][i - 1]][i - 1];
                dfs(y);
            }
        }
    }
    void build(vector<tuple<int, int, int>> E, int n) {
        sort(all(E));
        FOR(i, n) fa[i] = i, val[i] = son[i][0] = son[i][1] = 0;
        lg = __lg(n);
        for(auto [w, x, y]: E) {
            x = get(x); y = get(y);
            if(x ^ y) {
                son[++n][0] = x;
                son[  n][1] = y;
                fa[x] = fa[y] = fa[n] = n;
                val[n] = w;
            }
        }
        REP(i, 1, n) if(fa[i] == i) { // 每个连通块
            dep[i] = 1;
            memset(F[i], 0, sizeof(F[i]));
            dfs(i);
        }
    }
    int lca(int x, int y) {
        if(dep[x] < dep[y]) swap(x, y);
        for(int k = dep[x] - dep[y], i = 0; k; i++, k >>= 1)
            if(k & 1) x = F[x][i];
        if(x == y) return x;
        for(int i = lg; i >= 0; i--)
            if(F[x][i] != F[y][i]) x = F[x][i], y = F[y][i];
        return F[x][0];
    }
    int ask(int x, int y) {
        if(inf_id[x] || inf_id[y]) return -1;
        if(get(x) != get(y)) return -1;
        return val[lca(x, y)];
    }
}

namespace SL { // Scanning Line
    db nowx;
    struct Seg {
        P x, y; db k; int w;
        Seg() {}
        Seg(P x, P y, int w):x(x), y(y), w(w) {k = (y - x).slope();}
        db val() const {return x.y + k * (nowx - x.x);}
        bool operator <(Seg b) const {
            // db u = val(), v = b.val();
            // if(sign(u - v)) return u < v;
            // return k < b.k;
            return (y - x) * ((b.x + b.y) - (x + y)) > eps; // 叉积
        }
        bool operator ==(Seg b) const {
            return sign((y - x) * (b.y - b.x)) == 0;
        }
    };
    // set<Seg>::iterator seg_it[N];
    set<Seg> S;
    
    int ans[N];
    
    void solve() {
        qr(q);
        db x, y;
        VT<tuple<db, db, int>> Q;
        for(int i = 0; i < 2 * q; i++) {
            scanf("%lf %lf", &x, &y);
            Q.emplace_back(x, y, i);
        }
        sort(all(Q));
        VT<pair<db, int>> E;
        rep(k, 0, len - 1) {
            int u = e[k].u, v = e[k].v;
            if(p[u].x + 2 * eps < p[v].x) {
                E.emplace_back(p[u].x + eps, k + 1);
                E.emplace_back(p[v].x - eps, -(k + 1));
            }
        }
        sort(all(E));
        int ep = 0;
        inf_id[0] = 1;
        for(auto [x, y, id]: Q) {
            while(ep < SZ(E) && E[ep].fi <= x) {
                nowx = E[ep].fi;
                int k = E[ep++].se;
                // if(k > 0) k--, seg_it[k] = S.insert(Seg(p[e[k].u], p[e[k].v], near[k ^ 1])).fi;
                // else S.erase(seg_it[-k - 1]);
                if(k > 0) k--, S.insert(Seg(p[e[k].u], p[e[k].v], near[k ^ 1]));
                else k = -k - 1, S.erase(Seg(p[e[k].u], p[e[k].v], near[k ^ 1]));
            }
            nowx = x;
            P a(x - eps, y), b(x + eps, y);
            auto it = S.lower_bound(Seg(a, b, 0));
            if(it == S.end()) ans[id] = 0;
            else ans[id] = it->w;
        }
    }
}

int main() {
    qr(n, m);
    FOR(i, n) qr(p[i].x, p[i].y);
    RD::solve();
    {
        VT<tuple<int, int, int>> E;
        for(int i = 1; i < len; i += 2) {
        	int x = near[i - 1], y = near[i];
        	if(!inf_id[x] && !inf_id[y])
        		E.emplace_back(e[i].w, x, y);
        }
        MST::build(E, num);
    }
    SL::solve();
    for(int i = 0; i < 2 * q; i += 2) pr2(MST::ask(SL::ans[i], SL::ans[i + 1]));
    return 0;
}