bzoj 3051.cpp

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>
#include <set>
#define maxn 100010
#define eps (1e-10)
#define pi 3.1415926535898
#define tpi 6.2831853071796
using namespace std;
struct point {
    double x,y;
    point (double x = 0, double y = 0) : x(x) , y(y) {}
    void read() { scanf("%lf %lf",&x,&y); }
};
 
struct seg { point A,B,v; seg *nex; int num,sou,cost,done; double ang; } se[maxn << 1],*just[maxn << 1];;
struct poly { double s; seg *first; };
struct str { seg *val; str *nex; };
struct tstr { int u,v,nex,cost; };
struct ts { point P; int num,sou; };
point operator + (point a,point b) { return point(a.x + b.x, a.y + b.y); }
point operator - (point a,point b) { return point(a.x - b.x, a.y - b.y); }
point operator * (point a,double b) { return point(a.x * b,a.y * b); }
double operator * (point a,point b) { return a.x * b.x + a.y * b.y; }
double operator / (point a,point b) { return a.x * b.y - a.y * b.x; }
 
double length(point a) { return sqrt(a * a); }
 
double cl;
 
int sig(double a) {
    return (a < -eps ? -1 : a > eps);
}
 
double cross(seg &se) {
    double t = (cl - se.A.x) / se.v.x;
    return se.A.y + se.v.y * t;
}
 
struct stnode {
    int a;
    bool operator < (stnode b) {
        double A = cross(se[a]),B = cross(se[b.a]);
        return (sig(A - B) < 0 || (sig(A - B) == 0 && a < b.a));
    }
    /*bool operator == (stnode b) {
        return (a == b.a);
        }*/
    /*bool operator != (stnode b) {
        return (a != b.a);
        }*/
    stnode (int a = 0) : a(a) {}
};
 
struct cmp {
    bool operator () (stnode a,stnode b) {
        double A = cross(se[a.a]),B = cross(se[b.a]);
        return (sig(A - B) < 0 || (sig(A - B) == 0 && a.a < b.a));
    }
};
 
set <stnode,cmp> st;
typedef set <stnode> :: iterator poi;
 
bool edgecmp (tstr a,tstr b) {
    return (a.cost < b.cost);
}
 
queue <int> que;
struct MST {
    int i,j,k,l,m,n,e,f[maxn],fa[maxn],top,a,b;
    int s[maxn][21],t[maxn][21],first[maxn],deep[maxn];
    tstr edge[maxn << 2];
    MST () { e = 0; }
    void insert(int a,int b,int cost) {
        edge[++e].u = a; edge[e].v = b; edge[e].cost = cost;
    }
 
    int find(int a) {
        return (fa[a] == a ? a : (fa[a] = find(fa[a])));
    }
 
    void make_edge(int a,int b,int cost) {
        edge[++e].nex = first[a]; first[a] = e;
        edge[e].v = b; edge[e].cost = cost;
        edge[++e].nex = first[b]; first[b] = e;
        edge[e].v = a; edge[e].cost = cost;
    }
 
    void bfs(int u) {
        que.push(u);
        while (!que.empty()) {
            u = que.front(); que.pop();
            for (int i = first[u]; i; i = edge[i].nex) {
                if (f[u] == edge[i].v) continue;
                f[edge[i].v] = u; s[edge[i].v][0] = u;
                t[edge[i].v][0] = edge[i].cost;
                deep[edge[i].v] = deep[u] + 1;
                que.push(edge[i].v);
            }
        }
    }
     
    void init() {
        for (int j = 1; j <= 20; j++) {
            for (int i = 1; i <= n; i++) {
                s[i][j] = s[s[i][j - 1]][j - 1];
                t[i][j] = max(t[s[i][j - 1]][j - 1],t[i][j - 1]);
            }
        }
    }
     
    void get_() {
        sort(edge + 1,edge + e + 1,edgecmp);
        for (int i = 1; i <= n; i++) fa[i] = i;
        top = e;
        for (int i = 1; i <= top; i++) {
            a = edge[i].u; b = edge[i].v;
            find(a); find(b);
            if (fa[a] != fa[b]) {
                fa[fa[a]] = fa[b];
                make_edge(a,b,edge[i].cost);
            }
        }
         
        memset(f,0,sizeof(f));
        for (int i = 1; i <= n; i++) {
            if (!f[i]) bfs(i);
        }
        init();
    }
 
    int ask(int a,int b) {
        int i,j,ans = 0;
        if (!a || !b) return -1;
        find(a); find(b);
        if (fa[a] != fa[b]) return -1;
        if (deep[a] < deep[b]) swap(a,b);
        for (i = 20; s[a][i] && i >= 0; i--);
        while (deep[a] > deep[b]) {
            for (; deep[s[a][i]] < deep[b]; i--);
            ans = max(ans,t[a][i]);
            a = s[a][i];
        }
        for (i = 20; s[a][i] && i >= 0; i--);
        while (a != b) {
            for (; s[a][i] == s[b][i] && i; i--);
            ans = max(ans,max(t[a][i],t[b][i]));
            a = s[a][i]; b = s[b][i];
        }
        return ans;
    }
} B;
 
bool cmp(seg *a,seg *b) {
    return a -> ang > b -> ang;
}
 
bool pmc(seg *a,seg *b) {
    return (a -> B.x < b -> B.x);
}
 
bool askcmp(const ts &a,const ts &b) {
    return (a.P.x < b.P.x);
}
 
bool askpmc(const ts &a,const ts &b) {
    return (a.num < b.num);
}
 
struct graph {
    int tops,i,j,k,l,m,n,a,b,cost,tot,e;
    point dot[maxn];
    str *first[maxn], card[maxn << 1];
    poly land[maxn];
    ts ask[maxn << 1];
    graph () { tot = 1; }
 
    void build_seg(int a,int b,int cost) {
        se[++tot].A = dot[a]; se[tot].B = dot[b];
        se[tot].v = se[tot].B - se[tot].A;
        se[tot].num = tot; se[tot].cost = cost;
        se[tot].ang = acos(se[tot].v * point(1,0) / length(se[tot].v));
        if (sig(se[tot].v / point(1,0)) > 0) se[tot].ang = tpi - se[tot].ang;
        card[++e].nex = first[a]; first[a] = &card[e];
        card[e].val = &se[tot];
    }
     
    void get_next() {
        int top;
        for (int i = 1; i <= n; i++) {
            top = 0;
            for (str *k = first[i]; k; k = k -> nex)
                just[top++] = k -> val;
            sort(just,just + top,cmp);
            for (int j = 0; j < top; j++) se[just[j] -> num ^ 1].nex = just[(j + 1) % top];
        }
    }
 
    void get_s() {
        tops = 0;
        for (int i = 2; i <= tot; i++) {
            if (se[i].sou) continue;
            land[++tops].s = se[i].A / se[i].B;
            land[tops].first = &se[i];
            for (seg *k = land[tops].first -> nex; k != land[tops].first; k = k -> nex) {
                land[tops].s += k -> A / k -> B;
            }
            if (sig(land[tops].s) < 0) tops--;
            else {
                for (seg *k = land[tops].first -> nex; k != land[tops].first; k = k -> nex) {
                    k -> sou = tops;
                }
                land[tops].first -> sou = tops;
            }
        }
        for (int i = 2; i <= tot; i += 2) {
            if (se[i].sou && se[i ^ 1].sou) B.insert(se[i].sou,se[i ^ 1].sou,se[i].cost);
        }
        B.n = tops;
    }
 
    void scan_() {
        int n,top = 0,i,j,k,jop = 0,sz;
        double past = 0,now = 0; poi q;
        scanf("%d",&n);
        for (i = 1; i <= n; i++) {
            ask[++top].P.read(); ask[top].num = i;
            ask[++top].P.read(); ask[top].num = i;
        }
        sort(ask + 1,ask + top + 1,askcmp);
        jop = 1;
        for (i = 2; i <= tot; i++) {
            just[++jop] = &se[i];
        }
        sort(just + 2,just + jop + 1,pmc);
        k = 1; cl = 0;
        for (i = 2; i <= jop; i++) {
            for (j = i; j <= jop && !sig(just[i] -> B.x - just[j] -> B.x); j++) {
                if (!sig(just[j] -> A.x - just[j] -> B.x)) continue;
                if (just[j] -> num & 1) st.erase(stnode(just[j] -> num ^ 1));
                sz = st.size();
            }
            if (j > jop) break;
            cl = (just[i] -> B.x + just[j] -> B.x) / 2.0;
            for (j = i; j <= jop && !sig(just[i] -> B.x - just[j] -> B.x); j++) {
                if (!sig(just[j] -> A.x - just[j] -> B.x)) continue;
                if (!(just[j] -> num & 1)) st.insert(stnode(just[j] -> num));
                sz = st.size();
            }
            //for (poi qq = st.begin(); qq != st.end(); qq++) printf("%d ",qq -> a);
            //putchar('\n');
            for (; k <= top && sig(ask[k].P.x - just[i] -> B.x) < 0; k++);
            for (;k <= top && sig(ask[k].P.x - just[i] -> B.x) >= 0 && sig(ask[k].P.x - just[j] -> B.x) < 0; k++) {
                cl = ask[k].P.x;
                se[tot + 1].A = ask[k].P; se[tot + 1].v = point(1,0);
                q = st.lower_bound(stnode(tot + 1));
                if (q != st.end()) ask[k].sou = se[q -> a].sou;
            }
            i = --j;
        }
        sort(ask + 1,ask + top + 1,askpmc);
        for (i = 1; i <= top; i += 2) printf("%d\n",B.ask(ask[i].sou,ask[i + 1].sou));
    }
     
    void init() {
        scanf("%d %d",&n,&m);
        for (i = 1; i <= n; i++) dot[i].read();
        for (i = 1; i <= m; i++) {
            scanf("%d %d %d",&a,&b,&cost);
            if (sig((dot[b] - dot[a]) / point(0,1)) > 0) swap(a,b);
            build_seg(a,b,cost);
            build_seg(b,a,cost);
        }
        get_next();
        get_s();
        B.get_();
        scan_();
    }
} A;
     
int main() {
    A.init();
}