锐客网

  1. 首页 > it技术 > >

[wc2013]平面图

题目

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define UNS unsigned #define int64 long long #ifdef WIN32 #define fmt64 "%I64d" #else #define fmt64 "%lld" #endif #define oo 0x13131313 #define iter iterator #define PB push_back #define MP make_pair #define fst first #define snd second #define eps 1e-10 #define maxn 400005 #define REP(i, n) for (i = 0; i < (n); ++i) #define TR(i, a) for (i = a.begin(); i != a.end(); ++i) #define dual(e) (mem + (((e) - mem) ^ 1)) #define setc(p, d, q) (f[c[d][p] = q] = p)template inline bool minim(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template inline bool maxim(T &a, const T &b) { return b > a ? a = b, 1 : 0; } template inline T sqr(const T &a) { return a * a; } template inline T gcd(T x, T y) { for (T t; x; t = x, x = y % x, y = t); return y; }using namespace std; namespace geom { struct point { double x, y; point() { memset(this, 0, sizeof(point)); } point(const double &a, const double &b) : x(a), y(b) {} }; double operator *(const point &a, const point &b) { return a.x * b.y - a.y * b.x; } point operator -(const point &a, const point &b) { return point(a.x - b.x, a.y - b.y); } bool lower(point a, point b, const point &c) { if (a.x > b.x) swap(a, b); return (c - a) * (b - a) > -eps; } bool lower(point a, point b, point c, point d) { if (a.x > b.x) swap(a, b); if (c.x > d.x) swap(c, d); double mid = (min(b.x, d.x) + max(a.x, c.x)) / 2; a.y += (mid - a.x) / (b.x - a.x) * (b.y - a.y), a.x = mid; return lower(c, d, a); } }struct edge { int s, t, w, p; double slope; vector ::iter i; }; typedef vector graph; typedef vector 【[wc2013]平面图】 > graph1; typedef int arr_int[maxn]; typedef bool arr_bool[maxn]; geom::point points[maxn]; edge mem[maxn], *eptr = mem + 2; graph adj[maxn]; graph1 adjc[maxn]; int n, m, Q, vtot, ptot, inf; arr_int p, dgr, A, B, ufs, low, locate; arr_bool erase_V, erase_E, vst, q; void link(int u, int v, int h, int p) { geom::point q = points[v] - points[u]; *eptr = (edge) {u, v, h, p, atan2( q.y,q.x)}, adj[u].PB(eptr++); *eptr = (edge) {v, u, h, p, atan2(-q.y, -q.x)}, adj[v].PB(eptr++); ++dgr[u], ++dgr[v]; }void link1(int u, int v, int w) { adjc[u].PB(MP(v, w)), adjc[v].PB(MP(u, w)); }int get_ask() { q[++ptot] = 1, cin >> points[ptot].x >> points[ptot].y; return ptot; }namespace init_graph { arr_int s, t, w, p; int etot; bool nicere(edge *u, edge *v) { return u->slope < v->slope; } void erase_single(int u) { graph::iter j; for (; ; ) { erase_V[u] = 1; TR(j, adj[u]) { int v = (*j)->t; if (!erase_V[v] && --dgr[v] == 1) { u = v; break; } } if (j == adj[u].end()) return; } } graph::iter prev(graph &g, graph::iter j) { for (; ; ) { if (j == g.begin()) j = g.end(); if (!erase_V[(*(--j))->t]) return j; } } void build_graph(edge *fr) { graph::iter j; edge *f = fr, *e; double area = 0; ++vtot; for (; ; f = e) { area += points[f->s] * points[f->t]; /*judge of infinite*/ int u = f->t; e = *prev(adj[u], dual(f)->i); vst[e - mem] = 1, ufs[e - mem] = vtot; if (ufs[(e - mem) ^ 1]) s[etot] = vtot, t[etot] = ufs[(e - mem) ^ 1], p[etot] = etot, w[etot++] = e->w; /*link edges of dual graph*/ if (e == fr) break; } if (area < 0) inf = vtot; /*infinite*/ } void main() { int i; graph::iter j; for (i = 1; i <= n; ++i) if (dgr[i] == 1) erase_single(i); for (i = 1; i <= n; ++i) if (!erase_V[i]) { sort(adj[i].begin(), adj[i].end(), nicere); TR(j, adj[i]) (*j)->i = j; }for (edge *e = mem + 2; e < eptr; ++e) if (erase_V[e->s] || erase_V[e->t]) erase_E[(e - mem) >> 1] = 1; else if (!vst[e - mem]) build_graph(e); for (i = 1; i <= m; ++i) if (!erase_E[i]) low[i] = ufs[low[i]]; } }namespace splay { arr_int c[2], f; int root; void rotate(int p) { int q = f[p], k = p == c[0][q]; setc(f[q], q == c[1][f[q]], p), setc(q, !k, c[k][p]), setc(p, k, q); } void splay(int p, int tar = 0) { for (; f[p] != tar; rotate(p)) if (f[f[p]] != tar) rotate((p == c[0][f[p]]) ^ (f[p] == c[0][f[f[p]]]) ? p : f[p]); if (!tar) root = p; } void del(int p) { splay(p); if (!c[0][p]) f[root = c[1][p]] = 0; else if (!c[1][p]) f[root = c[0][p]] = 0; else { int prev, next; for (prev = c[0][p]; c[1][prev]; prev = c[1][prev]); for (next = c[1][p]; c[0][next]; next = c[0][next]); splay(prev), splay(next, prev), c[0][next] = 0; } } void insert(int l) { int p = root, q = 0, d = 0; for (; p; q = p, p = c[d][p]) d = lower(points[mem[l << 1].s], points[mem[l << 1].t], points[mem[p << 1].s], points[mem[p << 1].t]); setc(q, d, l); splay(l); } int find(const geom::point &x) { int p = root, q = inf, l = root; for (; p; ) if (geom::lower(points[mem[p << 1].s], points[mem[p << 1].t], x)) q = low[l = p], p = c[1][p]; else p = c[0][p]; return splay(l), q; } }namespace locate_graph { bool nicer(int i, int j) { return points[i].x < points[j].x; } void main() { int i; graph::iter j; REP (i, ptot) p[i] = i + 1; sort(p, p + ptot, nicer); REP (i, ptot) { int u = p[i]; if (q[u]) { locate[u] = splay::find (points[u]); } else { TR (j, adj[u]) if (!erase_E[*j - mem]) { if (points[u].x < points[(*j)->t].x) splay::insert((*j - mem) >> 1); else if (points[u].x > points [(*j)->t].x) splay::del((*j - mem) >> 1); } } } } }namespace MST_LCA { using namespace init_graph; arr_int f[18], g[18], dep, ufs; bool nicer(int u, int v) { return w[u] < w[v]; } int find(int x) { return ufs[x] == x ? x : ufs[x] = find(ufs[x]); } void dfs(int u, int fa) { graph1::iter j; dep[u] = dep[fa] + 1; TR(j, adjc[u]) if (j->fst != fa) { dfs(j->fst, u); f[0][j->fst] = u, g[0][j->fst] = j->snd; } } int get_ans(int u, int v) { int i, d, res = 0; if (dep[u] < dep[v]) swap(u, v); d = dep[u] - dep[v]; for (i = 0; d; d >>= 1, ++i) if (d & 1) maxim(res, g[i][u]), u = f[i][u]; if (u == v) return res; for (i = 17; ~i; --i) if (f[i][u] != f[i][v]) { maxim(res, g[i][u]), maxim(res, g[i][v]); u = f[i][u], v = f[i][v]; } return max(res, max(g[0][u], g[0][v])); } void prepare() { int i, j, k; for (i = 1; i <= vtot; ++i) ufs[i] = i; sort(init_graph::p, init_graph::p + etot, nicer); for (i = j = 0; i < etot && j < vtot - 1; ++i) { k = init_graph::p[i]; if (s[k] == inf || t[k] == inf || find(s[k]) == find(t[k])) continue; ufs[ufs[s[k]]] = ufs[t[k]]; link1(s[k], t[k], w[k]), ++j; }for (i = 1; i <= vtot; ++i) if (i != inf) { dfs(i, 0); break; }for (i = 1; i < 18; ++i) for (j = 1; j <= vtot; ++j) { f[i][j] = f[i - 1][f[i - 1][j]]; g[i][j] = max(g[i - 1][j], g[i - 1][f[i - 1][j]]); } } void main() { int i, a, b; prepare(); REP(i, Q) { a = locate[A[i]], b = locate[B[i]]; cout << (a == inf || b == inf ? -1 : get_ans(a, b)) << endl; } } }int main() { freopen("graph.in", "r", stdin); freopen("graph.out", "w", stdout); ios::sync_with_stdio(0); int i, j; cin >> n >> m; for (i = 1; i <= n; ++i) cin >> points[i].x >> points[i].y; for (j = 1; j <= m; ++j) { int u, v, h; cin >> u >> v >> h; link(u, v, h, i); low[j] = points[u].x < points[v].x ? j << 1 | 1 : j << 1; } init_graph::main(); cin >> Q; ptot = n; REP(i, Q) A[i] = get_ask(), B[i] = get_ask(); locate_graph::main(); MST_LCA::main(); }



    推荐阅读


    上一篇：[5]-变量-整型

    下一篇：STM32F4-UCOSIII-1移植