icpc_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ebi-fly13/icpc_library

:heavy_check_mark: test/geometry/Convex_Hull.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2827"
#define ERROR 0.001

#include "../../geometry/convex_hull.hpp"

#include "../../geometry/segment.hpp"
#include "../../template/template.hpp"
using namespace lib;

const ld dinf = 2e12;

void solve(int n) {
    vector<vector<vec>> a(n);
    vector<ld> hs(n);
    rep(i, 0, n) {
        int m;
        cin >> m >> hs[i];
        a[i].resize(m);
        rep(j, 0, m) {
            ld x, y;
            cin >> x >> y;
            a[i][j] = vec(x, y);
        }
    }
    ld rad1, rad2;
    cin >> rad1 >> rad2;
    rad1 *= M_PI / 180, rad2 *= M_PI / 180;
    ld sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    vec sv(sx, sy), tv(tx, ty);
    vector<vector<vec>> hulls(n);
    rep(i, 0, n) {
        vec pl = rot(vec(hs[i] / tanl(rad2), 0), rad1 + M_PI);
        vector<vec> b = a[i];
        rep(j, 0, a[i].size()) b.emplace_back(a[i][j] + pl);
        hulls[i] = convex_hull(b);
    }
    vector<vector<ld>> ds(n + 2, vector<ld>(n + 2, dinf));
    rep(i, 0, n) rep(j, 0, n) {
        if (i >= j) {
            ds[i][j] = ds[j][i];
            continue;
        }
        int si = hulls[i].size(), sj = hulls[j].size();
        rep(p, 0, si) rep(q, 0, sj) {
            segment iseg({hulls[i][p], hulls[i][(p + 1) % si]});
            segment jseg({hulls[j][q], hulls[j][(q + 1) % sj]});
            chmin(ds[i][j], dist(iseg, jseg));
        }
    }
    ds[n][n + 1] = abs(sv - tv);
    ds[n + 1][n] = ds[n][n + 1];
    auto dist_hull_vec = [&](int id, vec v) {
        bool in = true;
        ld res = dinf;
        int isiz = hulls[id].size();
        rep(i, 0, isiz) {
            vec iv = hulls[id][i];
            vec jv = hulls[id][(i + 1) % isiz];
            chmin(res, dist(segment({iv, jv}), v));
            if (cross(jv - iv, v - iv) < 0) in = false;
        }
        if (in) return ld(0);
        return res;
    };
    rep(i, 0, n) {
        ds[i][n] = dist_hull_vec(i, sv);
        ds[n][i] = ds[i][n];
        ds[i][n + 1] = dist_hull_vec(i, tv);
        ds[n + 1][i] = ds[i][n + 1];
    }
    vector<ld> ans(n + 2, dinf);
    ans[n] = 0;
    using pdi = pair<ld, int>;
    priority_queue<pdi, vector<pdi>, greater<pdi>> pque;
    pque.push(pdi(ans[n], n));
    while (!pque.empty()) {
        auto [idist, f] = pque.top();
        pque.pop();
        if (ans[f] < idist) continue;
        rep(i, 0, n + 2) {
            if (chmin(ans[i], idist + ds[f][i])) {
                pque.push(pdi(ans[i], i));
            }
        }
    }
    cout << ans[n + 1] << endl;
}

int main() {
    ldout();
    while (true) {
        int n;
        cin >> n;
        if (n == 0) break;
        solve(n);
    }
}
#line 1 "test/geometry/Convex_Hull.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2827"
#define ERROR 0.001

#line 2 "geometry/convex_hull.hpp"

#line 2 "geometry/base_ld.hpp"

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 4 "geometry/base_ld.hpp"

namespace lib {

using vec = complex<ld>;

const ld PI = acos(-1);

void ldout(int len = 20) {
    cout << fixed << setprecision(len);
}

int sgn(ld a, const ld eps = 1e-7) {
    return (a < -eps) ? -1 : (a > eps) ? 1 : 0;
}

bool same_vec(vec a, vec b) {
    a -= b;
    return sgn(a.real()) == 0 && sgn(a.imag()) == 0;
}

ld dot(const vec &a, const vec &b) {
    return (conj(a) * b).real();
}

ld cross(const vec &a, const vec &b) {
    return (conj(a) * b).imag();
}

int isp(const vec &a, const vec &b, const vec &c) {
    int cross_sgn = sgn(cross(b - a, c - a));
    if (cross_sgn == 0) {
        if (sgn(dot(b - a, c - a)) < 0) return -2;
        if (sgn(dot(a - b, c - b)) < 0) return 2;
    }
    return cross_sgn;
}

vec rot90(const vec &a) {
    return {-a.imag(), a.real()};
}

vec rot(const vec &a, ld rad) {
    return a * vec(cosl(rad), sinl(rad));
}

bool comp_for_argument_sort(const vec &lhs, const vec &rhs) {
    // if (abs(arg(lhs)-arg(rhs)) < eps) return false; // need ?
    return arg(lhs) < arg(rhs);
}

}  // namespace lib
#line 5 "geometry/convex_hull.hpp"

namespace lib {

vector<vec> convex_hull(vector<vec> a) {
    int n = a.size();
    if (n <= 2) return a;
    auto comp = [&](vec lhs, vec rhs) {
        if (lhs.real() == rhs.real()) return lhs.imag() < rhs.imag();
        return lhs.real() < rhs.real();
    };
    sort(all(a), comp);
    stack<int> uid, did;
    vec ri = a[n - 1];
    auto make_half = [&](bool isupper) {
        auto &id = (isupper ? uid : did);
        id.push(0);
        rep(i, 1, n - 1) {
            vec le = a[id.top()];
            auto cr = cross(ri - le, a[i] - le);
            if ((cr > 0 && isupper) || (cr < 0 && !isupper)) {
                while (id.size() >= 2) {
                    int test = id.top();
                    id.pop();
                    vec from = a[id.top()];
                    auto cr2 = cross(a[i] - from, a[test] - from);
                    if ((cr2 > 0 && isupper) || (cr2 < 0 && !isupper)) {
                        id.push(test);
                        break;
                    }
                }
                id.push(i);
            }
        }
    };
    make_half(true);
    make_half(false);
    vector<int> ids(1, n - 1);
    while (!did.empty()) ids.emplace_back(did.top()), did.pop();
    reverse(all(ids));
    while (!uid.empty()) ids.emplace_back(uid.top()), uid.pop();
    ids.pop_back();
    vector<vec> ans(ids.size());
    rep(i, 0, ids.size()) ans[i] = a[ids[i]];
    return ans;
}

}  // namespace lib
#line 5 "test/geometry/Convex_Hull.test.cpp"

#line 2 "geometry/segment.hpp"

#line 2 "geometry/line.hpp"

#line 4 "geometry/line.hpp"

namespace lib {

struct line {
    vec a, b;
};

vec proj(const line &l, const vec &p) {
    vec ab = l.b - l.a;
    return l.a + ab * (dot(ab, p - l.a) / norm(ab));
}

vec refl(const line &l, const vec &p) {
    return proj(l, p) * ld(2) - p;
}

int intersection(const line &a, const line &b) {
    if (sgn(cross(a.b - a.a, b.a - b.b)) != 0) {
        if (sgn(dot(a.b - a.a, b.a - b.b)) == 0) {
            return 1;
        }
        return 0;
    } else if (sgn(cross(a.b - a.a, b.a - a.a)) != 0) {
        return 2;
    } else {
        return 3;
    }
}

ld dist(const line &a, const vec &p) {
    return abs(cross(p - a.a, a.b - a.a) / abs(a.b - a.a));
}

vec cross_point(const line &a, const line &b) {
    assert(intersection(a, b) < 2);
    return a.a + (a.b - a.a) * cross(b.a - a.a, b.b - b.a) /
                     cross(a.b - a.a, b.b - b.a);
}

}  // namespace lib
#line 4 "geometry/segment.hpp"

namespace lib {

struct segment : line {};

bool intersection_segment_and_vec(const segment &a, const vec &p) {
    return isp(a.a, a.a, p) == 0;
}

bool intersection_segment(const segment &a, const segment &b) {
    if (sgn(isp(a.a, a.b, b.a) * isp(a.a, a.b, b.b)) <= 0 &&
        sgn(isp(b.a, b.b, a.a) * isp(b.a, b.b, a.b)) <= 0) {
        return true;
    } else
        return false;
}

vec cross_point(const segment &a, const segment &b) {
    assert(intersection_segment(a, b));
    return a.a + (a.b - a.a) * cross(b.a - a.a, b.b - b.a) /
                     cross(a.b - a.a, b.b - b.a);
}

ld dist(const segment &a, const vec &c) {
    if (sgn(dot(a.b - a.a, c - a.a)) <= 0) {
        return abs(c - a.a);
    } else if (sgn(dot(a.a - a.b, c - a.b)) <= 0) {
        return abs(c - a.b);
    } else {
        return abs(cross(c - a.a, a.b - a.a) / abs(a.b - a.a));
    }
}

ld dist(const segment &a, const segment &b) {
    if (intersection_segment(a, b))
        return 0;
    else
        return min(min(dist(a, b.a), dist(a, b.b)),
                   min(dist(b, a.a), dist(b, a.b)));
}

}  // namespace lib
#line 8 "test/geometry/Convex_Hull.test.cpp"
using namespace lib;

const ld dinf = 2e12;

void solve(int n) {
    vector<vector<vec>> a(n);
    vector<ld> hs(n);
    rep(i, 0, n) {
        int m;
        cin >> m >> hs[i];
        a[i].resize(m);
        rep(j, 0, m) {
            ld x, y;
            cin >> x >> y;
            a[i][j] = vec(x, y);
        }
    }
    ld rad1, rad2;
    cin >> rad1 >> rad2;
    rad1 *= M_PI / 180, rad2 *= M_PI / 180;
    ld sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    vec sv(sx, sy), tv(tx, ty);
    vector<vector<vec>> hulls(n);
    rep(i, 0, n) {
        vec pl = rot(vec(hs[i] / tanl(rad2), 0), rad1 + M_PI);
        vector<vec> b = a[i];
        rep(j, 0, a[i].size()) b.emplace_back(a[i][j] + pl);
        hulls[i] = convex_hull(b);
    }
    vector<vector<ld>> ds(n + 2, vector<ld>(n + 2, dinf));
    rep(i, 0, n) rep(j, 0, n) {
        if (i >= j) {
            ds[i][j] = ds[j][i];
            continue;
        }
        int si = hulls[i].size(), sj = hulls[j].size();
        rep(p, 0, si) rep(q, 0, sj) {
            segment iseg({hulls[i][p], hulls[i][(p + 1) % si]});
            segment jseg({hulls[j][q], hulls[j][(q + 1) % sj]});
            chmin(ds[i][j], dist(iseg, jseg));
        }
    }
    ds[n][n + 1] = abs(sv - tv);
    ds[n + 1][n] = ds[n][n + 1];
    auto dist_hull_vec = [&](int id, vec v) {
        bool in = true;
        ld res = dinf;
        int isiz = hulls[id].size();
        rep(i, 0, isiz) {
            vec iv = hulls[id][i];
            vec jv = hulls[id][(i + 1) % isiz];
            chmin(res, dist(segment({iv, jv}), v));
            if (cross(jv - iv, v - iv) < 0) in = false;
        }
        if (in) return ld(0);
        return res;
    };
    rep(i, 0, n) {
        ds[i][n] = dist_hull_vec(i, sv);
        ds[n][i] = ds[i][n];
        ds[i][n + 1] = dist_hull_vec(i, tv);
        ds[n + 1][i] = ds[i][n + 1];
    }
    vector<ld> ans(n + 2, dinf);
    ans[n] = 0;
    using pdi = pair<ld, int>;
    priority_queue<pdi, vector<pdi>, greater<pdi>> pque;
    pque.push(pdi(ans[n], n));
    while (!pque.empty()) {
        auto [idist, f] = pque.top();
        pque.pop();
        if (ans[f] < idist) continue;
        rep(i, 0, n + 2) {
            if (chmin(ans[i], idist + ds[f][i])) {
                pque.push(pdi(ans[i], i));
            }
        }
    }
    cout << ans[n + 1] << endl;
}

int main() {
    ldout();
    while (true) {
        int n;
        cin >> n;
        if (n == 0) break;
        solve(n);
    }
}
Back to top page