cp-documentation

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

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: Test/AOJ/2827.test.cpp

Depends on

Code

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

#include "../../Src/GeometryR2/Angle.hpp"
#include "../../Src/GeometryR2/PointCloud.hpp"
#include "../../Src/GeometryR2/Polygon.hpp"
#include "../../Src/GeometryR2/ConvexHull.hpp"
#include "../../Src/GeometryR2/Distance/SegmentAndSegment.hpp"
#include "../../Src/GeometryR2/Contain/ConvexPolygonContainsPoint.hpp"
using namespace zawa::geometryR2;

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <queue>
int N, NV[100];
Real H[100], THETA, GAMMA;
Polygon P[100];
Point START, GOAL;
bool inner(const Polygon& p, const Polygon& q) {
    for (int i = 0 ; i < std::ssize(p) ; i++) if (ConvexPolygonContainsPoint(q, p[i]) == OUTSIDE) return false;
    return true;
}
Real Distance(const Polygon& p, const Polygon& q) {
    if (inner(p, q) or inner(q, p)) return 0;
    Real res = 1e18l;
    for (int i = 0 ; i < std::ssize(p) ; i++) for (int j = 0 ; j < std::ssize(q) ; j++) {
        res = std::min(res, Distance(Segment{p[i], p[i+1==std::ssize(p)?0:i+1]},
                    Segment{q[j], q[j+1==std::ssize(q)?0:j+1]}));
    }
    return res;
}
Real NaiveDistance(const Polygon& poly, const Point& p) {
    if (ConvexPolygonContainsPoint(poly, p) != OUTSIDE) {
        return 0;
    }
    else {
        Real res = 1e18l;
        for (int i = 0 ; i < std::ssize(poly) ; i++) {
            res = std::min(res, Distance(p, Segment{poly[i], poly[i+1==std::ssize(poly)?0:i+1]}));
        }
        return res;
    }
}
Real solve() {
    std::vector<Polygon> hulls = [&]() {
        std::vector<PointCloud> pcs(N);
        std::vector<Polygon> res(N);
        for (int i = 0 ; i < N ; i++) {
            const Real shadow_len = H[i] * cosl(GAMMA) / sinl(GAMMA);
            for (int j = 0 ; j < NV[i] ; j++) {
                pcs[i].push_back(P[i][j]);
                pcs[i].push_back(P[i][j] - shadow_len * Point{cosl(THETA), sinl(THETA)});
            }
            res[i] = ConvexHull<true>(pcs[i]);
            assert(std::ssize(res[i]) >= 3);
            res[i].normalForm();
        }
        return res;
    }();
    const int n = N + 2, st = N, go = N + 1;
    std::vector g(n, std::vector<Real>(n));
    for (int i = 0 ; i < N ; i++) {
        const Real w = NaiveDistance(hulls[i], START);
        g[st][i] = g[i][st] = w;
    }
    for (int i = 0 ; i < N ; i++) {
        const Real w = NaiveDistance(hulls[i], GOAL);
        g[go][i] = g[i][go] = w;
    }
    g[st][go] = g[go][st] = Distance(START, GOAL);
    for (int i = 0 ; i < N ; i++) {
        for (int j = i + 1 ; j < N ; j++) {
            g[i][j] = g[j][i] = Distance(hulls[i], hulls[j]);
        }
    }
    std::vector<Real> dist(n, 1e18l);
    using qt = std::pair<Real, int>;
    std::priority_queue<qt, std::vector<qt>, std::greater<qt>> que;
    dist[st] = 0;
    que.push({dist[st], st});
    // for (int i = 0 ; i < n ; i++) {
    //     for (int j = 0 ; j < n ; j++) std::cout << g[i][j] << ' ';
    //     std::cout << std::endl;
    // }
    while (que.size()) {
        auto [d, v] = que.top();
        que.pop();
        if (Bigger(d, dist[v])) continue;
        for (int i = 0 ; i < n ; i++) if (Smaller(d + g[v][i], dist[i])) {
            dist[i] = d + g[v][i];
            que.push({dist[i], i});
        }
    }
    return dist[go];
}
int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(5);
    while (true) {
        std::cin >> N;
        if (N == 0) break;
        for (int i = 0 ; i < N ; i++) {
            std::cin >> NV[i] >> H[i];
            Polygon p(NV[i]);
            for (int j = 0 ; j < NV[i] ; j++) std::cin >> p[j].x() >> p[j].y();
            P[i] = std::move(p);
        }
        std::cin >> THETA >> GAMMA;
        THETA = ArcToRadian(THETA);
        GAMMA = ArcToRadian(GAMMA);
        std::cin >> START.x() >> START.y() >> GOAL.x() >> GOAL.y();
        std::cout << solve() << '\n';
    }
}
#line 1 "Test/AOJ/2827.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2827"
#define ERROR 0.001

#line 2 "Src/GeometryR2/Angle.hpp"

#line 2 "Src/GeometryR2/Real.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/GeometryR2/Real.hpp"

#include <cmath>
#include <cassert>

namespace zawa {

namespace geometryR2 {

using Real = long double;

namespace internal {

Real EPS{1e-12};
constexpr i32 negative{-1};
constexpr i32 zero{};
constexpr i32 positive{1};

} // namespace internal

Real& Eps() {
    return internal::EPS;
}

i32 Sign(Real value) {
    if (value < -Eps()) return internal::negative;
    if (value > Eps()) return internal::positive;
    return internal::zero;
}

bool Zero(Real value) {
    return Sign(value) == internal::zero;
}

bool Positive(Real value) {
    return Sign(value) == internal::positive;
}

bool Negative(Real value) {
    return Sign(value) == internal::negative;
}

bool Equal(Real a, Real b) {
    return Zero(a - b);
}

bool Smaller(Real a, Real b) {
    return Negative(a - b);
}

bool Bigger(Real a, Real b) {
    return Positive(a - b);
}

Real Square(Real value) {
    return (Zero(value) ? value : value * value);
}

Real Sqrt(Real value) {
    assert(!Negative(value));
    return (Zero(value) ? value : sqrtl(value));
}

Real Abs(Real value) {
    return (Negative(value) ? -value : value);
}

} // namespace geometryR2
 
} // namespace zawa
#line 4 "Src/GeometryR2/Angle.hpp"

#line 6 "Src/GeometryR2/Angle.hpp"

namespace zawa {

namespace geometryR2 {

constexpr Real PI{acosl(-1)};
constexpr Real TAU{static_cast<Real>(2) * PI};

constexpr Real ArcToRadian(Real arc) {
    return (arc * PI) / static_cast<Real>(180);
}

constexpr Real RadianToArc(Real radian) {
    return (radian * static_cast<Real>(180)) / PI;
}

} // namespace geometryR2

} // namespace zawa
#line 2 "Src/GeometryR2/PointCloud.hpp"

#line 2 "Src/GeometryR2/Point.hpp"

#line 5 "Src/GeometryR2/Point.hpp"

#line 7 "Src/GeometryR2/Point.hpp"
#include <iostream>
#line 9 "Src/GeometryR2/Point.hpp"

namespace zawa {

namespace geometryR2 {

class Point {
private:
    Real x_{}, y_{};
public:
    /* constructor */
    Point() = default;
    Point(Real x, Real y) : x_{x}, y_{y} {}

    /* getter, setter */
    Real x() const {
        return x_;
    }
    Real& x() {
        return x_;
    }
    Real y() const {
        return y_;
    }
    Real& y() {
        return y_;
    }

    /* operator */
    Point& operator+=(const Point& rhs) {
        x_ += rhs.x();
        y_ += rhs.y();
        return *this;
    }
    friend Point operator+(const Point& lhs, const Point& rhs) {
        return Point{lhs} += rhs;
    }
    Point operator+() const {
        return *this;
    }
    Point& operator-=(const Point& rhs) {
        x_ -= rhs.x();
        y_ -= rhs.y();
        return *this;
    }
    friend Point operator-(const Point& lhs, const Point& rhs) {
        return Point{lhs} -= rhs;
    }
    Point operator-() const {
        return Point{} - *this;
    }
    Point& operator*=(Real k) {
        x_ *= k;
        y_ *= k;
        return *this;
    }
    friend Point operator*(Real k, const Point& p) {
        return Point{p} *= k;
    }
    friend Point operator*(const Point& p, Real k) {
        return Point{p} *= k;
    }
    Point& operator/=(Real k) {
        assert(!Zero(k));
        x_ /= k;
        y_ /= k;
        return *this;
    }
    friend Point operator/(Real k, const Point& p) {
        return Point{p} /= k;
    }
    friend Point operator/(const Point& p, Real k) {
        return Point{p} /= k;
    }
    friend bool operator==(const Point& lhs, const Point& rhs) {
        return Equal(lhs.x(), rhs.x()) and Equal(lhs.y(), rhs.y());
    }
    friend bool operator!=(const Point& lhs, const Point& rhs) {
        return !Equal(lhs.x(), rhs.x()) or !Equal(lhs.y(), rhs.y());
    }
    friend bool operator<(const Point& lhs, const Point& rhs) {
        return Smaller(lhs.x(), rhs.x()) or 
            (Equal(lhs.x(), rhs.x()) and Smaller(lhs.y(), rhs.y()));
    }
    friend bool operator<=(const Point& lhs, const Point& rhs) {
        return Smaller(lhs.x(), rhs.x()) or 
            (Equal(lhs.x(), rhs.x()) and (Smaller(lhs.y(), rhs.y()) or Equal(lhs.y(), rhs.y())));
    }
    friend bool operator>(const Point& lhs, const Point& rhs) {
        return Bigger(lhs.x(), rhs.x()) or
            (Equal(lhs.x(), rhs.x()) and Bigger(lhs.y(), rhs.y()));
    }
    friend bool operator>=(const Point& lhs, const Point& rhs) {
        return Bigger(lhs.x(), rhs.x()) or
            (Equal(lhs.x(), rhs.x()) and (Bigger(lhs.y(), rhs.y()) or Equal(lhs.y(), rhs.y())));
    }
    friend std::istream& operator>>(std::istream& is, Point& p) {
        is >> p.x_ >> p.y_;
        return is;
    }
    friend std::ostream& operator<<(std::ostream& os, const Point& p) {
        os << '(' << p.x_ << ',' << p.y_ << ')';
        return os;
    }
    
    /* member function */
    Real normSquare() const {
        return Square(x_) + Square(y_);
    }
    Real norm() const {
        return Sqrt(normSquare());
    }
    void normalize() {
        assert((*this) != Point{});
        (*this) /= norm(); 
    }
    Point normalized() const {
        Point res{*this};
        res.normalize();
        return res;
    }
    Point rotated(Real radian) const {
        return Point{
            x_ * cosl(radian) - y_ * sinl(radian),
            x_ * sinl(radian) + y_ * cosl(radian)
        };
    }
    void rotate(Real radian) {
        *this = rotated(radian); 
    }
    Point rotatedByArc(Real arc) const {
        return rotated(ArcToRadian(arc));
    }
    void rotateByArc(Real arc) {
        *this = rotatedByArc(arc);
    }
    Real argument() const {
        return (Negative(y_) ? TAU : static_cast<Real>(0)) + atan2l(y_, x_);
    }
    Real argumentByArc() const {
        return RadianToArc(argument());
    }

    /* friend function */
    friend Real Dot(const Point& lhs, const Point& rhs) {
        return lhs.x() * rhs.x() + lhs.y() * rhs.y();
    }
    friend Real Cross(const Point& lhs, const Point& rhs) {
        return lhs.x() * rhs.y() - lhs.y() * rhs.x();
    }
    friend Real Argument(const Point& lhs, const Point& rhs) {
        return rhs.argument() - lhs.argument();
    }
    friend bool ArgComp(const Point& lhs, const Point& rhs) {
        return Smaller(lhs.argument(), rhs.argument());
    }
};

using Vector = Point;

} // namespace geometryR2

} // namespace zawa
#line 4 "Src/GeometryR2/PointCloud.hpp"

#include <vector>

namespace zawa {

namespace geometryR2 {

using PointCloud = std::vector<Point>;

} // namespace geometryR2

} // namespace zawa
#line 2 "Src/GeometryR2/Polygon.hpp"

#line 2 "Src/GeometryR2/Relation.hpp"

#line 5 "Src/GeometryR2/Relation.hpp"

namespace zawa {

namespace geometryR2 {

enum RELATION {
    // p0 -> p1 -> p2の順で直線上に並んでいる
    ONLINE_FRONT = -2,
    // (p1 - p0) -> (p2 - p0)が時計回りになっている
    CLOCKWISE,
    // p0 -> p2 -> p1の順で直線上に並んでいる
    ON_SEGMENT,
    // (p1 - p0) -> (p2 - p0)が反時計回りになっている
    COUNTER_CLOCKWISE,
    // p2 -> p0 -> p1、またはp1 -> p0 -> p2の順で直線上に並んでいる
    ONLINE_BACK
};

RELATION Relation(const Point& p0, const Point& p1, const Point& p2) {
    Point a{p1 - p0}, b{p2 - p0};
    if (Positive(Cross(a, b))) return COUNTER_CLOCKWISE;
    if (Negative(Cross(a, b))) return CLOCKWISE;
    if (Negative(Dot(a, b))) return ONLINE_BACK;
    if (Smaller(a.normSquare(), b.normSquare())) return ONLINE_FRONT;
    return ON_SEGMENT;
};

} // namespace geometryR2

} // namespace zawa
#line 7 "Src/GeometryR2/Polygon.hpp"

#include <algorithm>
#line 10 "Src/GeometryR2/Polygon.hpp"
#include <concepts>
#line 12 "Src/GeometryR2/Polygon.hpp"

namespace zawa {

namespace geometryR2 {

class Polygon {
private:
    std::vector<Point> data_;
public:
    /* member */
    usize size() const {
        return data_.size();
    }

    /* constructor */
    Polygon() = default;
    explicit Polygon(const std::vector<Point>& data) : data_{data} {}
    explicit Polygon(usize n) : data_(n) {}

    /* operator[] */
    Point& operator[](usize i) {
        assert(i < size());
        return data_[i];
    }
    const Point& operator[](usize i) const {
        assert(i < size());
        return data_[i];
    }
    friend std::istream& operator>>(std::istream& is, Polygon& polygon) {
        for (size_t i{} ; i < polygon.size() ; i++) {
            is >> polygon[i];
        }
        return is;
    }
    friend std::ostream& operator<<(std::ostream& os, const Polygon& polygon) {
        for (usize i{} ; i < polygon.size() ; i++) {
            std::cout << polygon[i] << (i + 1 == polygon.size() ? "" : " ");
        }
        return os;
    }

    /* member function */
    void orderRotate(usize i) {
        assert(i < size());
        std::rotate(data_.begin(), data_.begin() + i, data_.end());
    }
    void normalForm() {
        auto index{std::distance(data_.begin(), std::min_element(data_.begin(), data_.end()))};
        orderRotate(index);
    }
    Polygon normalFormed() const {
        Polygon res{*this};
        res.normalForm();
        return res;
    }
    bool isConvex() const {
        assert(size() >= static_cast<usize>(3));
        for (usize i{} ; i < size() ; i++) {
            if (Relation(data_[i], data_[i+1==size()?0:i+1], data_[i+2>=size()?i+2-size():i+2])
                    == CLOCKWISE) {
                return false;
            }
        }
        return true;
    }
    Real area() const {
        if (std::ssize(data_) <= 2) return 0;
        Real res{};
        for (usize i{1} ; i < size() ; i++) {
            res += Cross(data_[i] - data_[0], data_[i+1==size()?0:i+1] - data_[0]);
        }
        return res / static_cast<Real>(2);
    }
    void pushBack(const Point& p) {
        data_.push_back(p);
    }
    void emplaceBack(Real x, Real y) {
        data_.emplace_back(x, y);
    }
    void reserve(usize n) {
        data_.reserve(n);
    }
    template <std::input_iterator RandomAccessIterator>
    void insert(usize n, RandomAccessIterator first, RandomAccessIterator last) {
        assert(n <= size());
        data_.insert(std::next(data_.begin(), n), first, last);
    }
};

} // namespace geometryR2

} // namespace zawa

#line 2 "Src/GeometryR2/ConvexHull.hpp"

#line 7 "Src/GeometryR2/ConvexHull.hpp"

#line 10 "Src/GeometryR2/ConvexHull.hpp"
#include <iterator>
#line 12 "Src/GeometryR2/ConvexHull.hpp"

namespace zawa {

namespace geometryR2 {

template <bool strictly>
Polygon ConvexHull(const PointCloud& p) {
    PointCloud cp{p};
    std::sort(cp.begin(), cp.end());
    cp.erase(std::unique(cp.begin(), cp.end()), cp.end());
    if (cp.size() <= 2u) {
        return Polygon{cp};
    }
    PointCloud lower;
    lower.reserve(p.size());
    for (auto it{cp.begin()} ; it != cp.end() ; it++) {
        lower.push_back(*it);
        while (lower.size() >= 3u) {
            if (Relation(lower[lower.size() - 3], lower[lower.size() - 2], lower[lower.size() - 1]) == COUNTER_CLOCKWISE) {
                break;
            }
            if constexpr (!strictly) {
                if (Relation(lower[lower.size() - 3], lower[lower.size() - 2], lower[lower.size() - 1]) == ONLINE_FRONT) {
                    break;
                }
            }
            std::swap(lower[lower.size() - 2], lower[lower.size() - 1]);
            lower.pop_back();
        }
    }
    PointCloud upper;
    upper.reserve(p.size());
    for (auto it{cp.rbegin()} ; it != cp.rend() ; it++) {
        upper.push_back(*it);
        while (upper.size() >= 3u) {
            if (Relation(upper[upper.size() - 3], upper[upper.size() - 2], upper[upper.size() - 1]) == COUNTER_CLOCKWISE) {
                break;
            }
            if constexpr (!strictly) {
                if (Relation(upper[upper.size() - 3], upper[upper.size() - 2], upper[upper.size() - 1]) == ONLINE_FRONT) {
                    break;
                }
            }
            std::swap(upper[upper.size() - 2], upper[upper.size() - 1]);
            upper.pop_back();
        }
    }

    Polygon res;
    res.reserve(lower.size() + upper.size() - 2);
    res.insert(res.size(), lower.begin(), lower.end());
    res.insert(res.size(), std::next(upper.begin()), std::prev(upper.end()));
    return res;
}

} // namespace geometryR2

} // namespace zawa
#line 2 "Src/GeometryR2/Distance/SegmentAndSegment.hpp"

#line 2 "Src/GeometryR2/Segment.hpp"

#line 2 "Src/GeometryR2/Distance/PointAndPoint.hpp"

#line 4 "Src/GeometryR2/Distance/PointAndPoint.hpp"

namespace zawa {

namespace geometryR2 {

Real Distance(const Point& p0, const Point& p1) {
    return Point{p1 - p0}.norm();
}

Real DistanceSquare(const Point& p0, const Point& p1) {
    return Point{p1 - p0}.normSquare();
}

} // namespace geometryR2

} // namespace zawa
#line 6 "Src/GeometryR2/Segment.hpp"

#line 9 "Src/GeometryR2/Segment.hpp"

namespace zawa {

namespace geometryR2 {

class Segment {
private:
    Point p0_{}, p1_{};
public:
    /* constructor */
    Segment() = default;
    Segment(const Point& p0, const Point& p1) : p0_{p0}, p1_{p1} {}
    Segment(Real x0, Real y0, Real x1, Real y1) : p0_{x0, y0}, p1_{x1, y1} {}

    /* getter setter */
    const Point& p0() const {
        return p0_;
    }
    Point& p0() {
        return p0_;
    }
    const Point& p1() const {
        return p1_;
    }
    Point& p1() {
        return p1_;
    }

    /* member function */
    bool valid() const {
        return p0_ != p1_;
    }
    bool straddle(const Segment& s) const {
        return Relation(p0_, p1_, s.p0()) * Relation(p0_, p1_, s.p1()) <= 0;
    }
    Real length() const {
        assert(valid());
        return Distance(p0_, p1_);
    }
    Point midpoint() const {
        assert(valid());
        return p0_ + Vector{p1_ - p0_} / static_cast<Real>(2);
    }
};

} // namespace geometryR2

} // namespace zawa
#line 2 "Src/GeometryR2/Intersect/SegmentAndSegment.hpp"

#line 4 "Src/GeometryR2/Intersect/SegmentAndSegment.hpp"

#line 6 "Src/GeometryR2/Intersect/SegmentAndSegment.hpp"

namespace zawa {

namespace geometryR2 {

bool Intersect(const Segment& s0, const Segment& s1) {
    assert(s0.valid());
    assert(s1.valid());
    return s0.straddle(s1) and s1.straddle(s0);
}

} // namespace geometryR2

} // namespace zawa
#line 2 "Src/GeometryR2/Distance/PointAndSegment.hpp"

#line 7 "Src/GeometryR2/Distance/PointAndSegment.hpp"

#line 9 "Src/GeometryR2/Distance/PointAndSegment.hpp"

namespace zawa {

namespace geometryR2 {

Real Distance(const Point& p, const Segment& s) {
    assert(s.valid());
    if (Negative(Dot(s.p1() - s.p0(), p - s.p0()))) {
        return Distance(p, s.p0());
    }
    if (Negative(Dot(s.p0() - s.p1(), p - s.p1()))) {
        return Distance(p, s.p1());
    }
    return Abs(Cross(s.p1() - s.p0(), p - s.p0())) / s.length();
}

bool PointOnSegment(const Point& p, const Segment& s) {
    assert(s.valid());
    return Zero(Distance(p, s));
}

} // namespace geometryR2

} // namespace zawa
#line 7 "Src/GeometryR2/Distance/SegmentAndSegment.hpp"

#line 9 "Src/GeometryR2/Distance/SegmentAndSegment.hpp"

namespace zawa {

namespace geometryR2 {

Real Distance(const Segment& s0, const Segment& s1) {
    assert(s0.valid());
    assert(s1.valid());
    if (Intersect(s0, s1)) {
        return static_cast<Real>(0);
    }
    else {
        return std::min({ 
                Distance(s1.p0(), s0), 
                Distance(s1.p1(), s0),
                Distance(s0.p0(), s1),
                Distance(s0.p1(), s1) });
    }
}

} // namespace geometryR2

} // namespace zawa
#line 2 "Src/GeometryR2/Contain/ConvexPolygonContainsPoint.hpp"

#line 2 "Src/Utility/BinarySearch.hpp"

#line 4 "Src/Utility/BinarySearch.hpp"

#line 6 "Src/Utility/BinarySearch.hpp"
#include <functional>
#include <type_traits>
#include <utility>

namespace zawa {

namespace internal {

template <class T>
T MidPoint(T a, T b) {
    if (a > b) std::swap(a, b);
    return a + ((b - a) >> 1);
}

template <class T>
T Abs(T a, T b) {
    return (a >= b ? a - b : b - a);
}

} // namespace zawa::internal

template <class T, class Function>
T BinarySearch(T ok, T ng, const Function& f) {
    static_assert(std::is_integral_v<T>, "T must be integral type");
    static_assert(std::is_convertible_v<Function, std::function<bool(T)>>, "f must be function bool(T)");
    while (internal::Abs(ok, ng) > 1) {
        T mid{ internal::MidPoint(ok, ng) };
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

template <class T, class Function>
T BinarySearch(T ok, T ng, const Function& f, u32 upperLimit) {
    static_assert(std::is_signed_v<T>, "T must be signed arithmetic type");
    static_assert(std::is_convertible_v<Function, std::function<bool(T)>>, "f must be function bool(T)");
    for (u32 _{} ; _ < upperLimit ; _++) {
        T mid{ (ok + ng) / (T)2 };
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

} // namespace zawa
#line 2 "Src/GeometryR2/Contain/State.hpp"

namespace zawa {

namespace geometryR2 {

enum ContainState {
    INSIDE,
    ONLINE,
    OUTSIDE
};

} // namespace geometryR2

} // namespace zawa
#line 9 "Src/GeometryR2/Contain/ConvexPolygonContainsPoint.hpp"

#line 11 "Src/GeometryR2/Contain/ConvexPolygonContainsPoint.hpp"

namespace zawa {

namespace geometryR2 {

namespace internal {

bool TriangleContainsPoint(const Point& p0, const Point& p1, const Point& p2, const Point& p) {
    Real area{Abs(Cross(p1 - p0, p2 - p0))};
    Real value{};
    value += Abs(Cross(p0 - p, p1 - p));
    value += Abs(Cross(p1 - p, p2 - p));
    value += Abs(Cross(p2 - p, p0 - p));
    return Equal(area, value);
}

} // namespace internal

// note: 凸多角形であることを確認してください。
// note: normal formにしておいてください
ContainState ConvexPolygonContainsPoint(const Polygon& polygon, const Point& p) {
    usize n{polygon.size()};
    assert(n >= static_cast<usize>(3));
    if (polygon[0] == p or polygon[1] == p or polygon[n - 1] == p) {
        return ONLINE;
    }
    if (Relation(polygon[0], polygon[1], p) == ON_SEGMENT) {
        return ONLINE;
    }
    if (Relation(polygon[0], polygon[n - 1], p) == ON_SEGMENT) {
        return ONLINE;
    }
    if (Zero(Cross(polygon[1] - polygon[0], p - polygon[0]))) {
        return OUTSIDE;
    }
    if (Zero(Cross(polygon[n - 1] - polygon[0], p - polygon[0]))) {
        return OUTSIDE;
    }
    if (!(Relation(polygon[0], polygon[1], p) == COUNTER_CLOCKWISE and Relation(polygon[0], p, polygon[n - 1]) == COUNTER_CLOCKWISE)) {
        return OUTSIDE;
    }

    auto f{[&](usize i) -> bool {
        return Relation(polygon[0], polygon[i], p) == COUNTER_CLOCKWISE;
    }};

    usize pos{BinarySearch(usize{0}, usize{n - 1}, f)};
    if (p == polygon[pos]) return ONLINE;
    if (p == polygon[pos + 1]) return ONLINE;
    if (Relation(polygon[pos], polygon[pos + 1], p) == ON_SEGMENT) return ONLINE;

    if (internal::TriangleContainsPoint(polygon[0], polygon[pos], polygon[pos + 1], p)) {
        return INSIDE;
    }
    else {
        return OUTSIDE;
    }
}

} // namespace geometryZ2

} // namespace zawa
#line 10 "Test/AOJ/2827.test.cpp"
using namespace zawa::geometryR2;

#line 13 "Test/AOJ/2827.test.cpp"
#include <iomanip>
#line 16 "Test/AOJ/2827.test.cpp"
#include <queue>
int N, NV[100];
Real H[100], THETA, GAMMA;
Polygon P[100];
Point START, GOAL;
bool inner(const Polygon& p, const Polygon& q) {
    for (int i = 0 ; i < std::ssize(p) ; i++) if (ConvexPolygonContainsPoint(q, p[i]) == OUTSIDE) return false;
    return true;
}
Real Distance(const Polygon& p, const Polygon& q) {
    if (inner(p, q) or inner(q, p)) return 0;
    Real res = 1e18l;
    for (int i = 0 ; i < std::ssize(p) ; i++) for (int j = 0 ; j < std::ssize(q) ; j++) {
        res = std::min(res, Distance(Segment{p[i], p[i+1==std::ssize(p)?0:i+1]},
                    Segment{q[j], q[j+1==std::ssize(q)?0:j+1]}));
    }
    return res;
}
Real NaiveDistance(const Polygon& poly, const Point& p) {
    if (ConvexPolygonContainsPoint(poly, p) != OUTSIDE) {
        return 0;
    }
    else {
        Real res = 1e18l;
        for (int i = 0 ; i < std::ssize(poly) ; i++) {
            res = std::min(res, Distance(p, Segment{poly[i], poly[i+1==std::ssize(poly)?0:i+1]}));
        }
        return res;
    }
}
Real solve() {
    std::vector<Polygon> hulls = [&]() {
        std::vector<PointCloud> pcs(N);
        std::vector<Polygon> res(N);
        for (int i = 0 ; i < N ; i++) {
            const Real shadow_len = H[i] * cosl(GAMMA) / sinl(GAMMA);
            for (int j = 0 ; j < NV[i] ; j++) {
                pcs[i].push_back(P[i][j]);
                pcs[i].push_back(P[i][j] - shadow_len * Point{cosl(THETA), sinl(THETA)});
            }
            res[i] = ConvexHull<true>(pcs[i]);
            assert(std::ssize(res[i]) >= 3);
            res[i].normalForm();
        }
        return res;
    }();
    const int n = N + 2, st = N, go = N + 1;
    std::vector g(n, std::vector<Real>(n));
    for (int i = 0 ; i < N ; i++) {
        const Real w = NaiveDistance(hulls[i], START);
        g[st][i] = g[i][st] = w;
    }
    for (int i = 0 ; i < N ; i++) {
        const Real w = NaiveDistance(hulls[i], GOAL);
        g[go][i] = g[i][go] = w;
    }
    g[st][go] = g[go][st] = Distance(START, GOAL);
    for (int i = 0 ; i < N ; i++) {
        for (int j = i + 1 ; j < N ; j++) {
            g[i][j] = g[j][i] = Distance(hulls[i], hulls[j]);
        }
    }
    std::vector<Real> dist(n, 1e18l);
    using qt = std::pair<Real, int>;
    std::priority_queue<qt, std::vector<qt>, std::greater<qt>> que;
    dist[st] = 0;
    que.push({dist[st], st});
    // for (int i = 0 ; i < n ; i++) {
    //     for (int j = 0 ; j < n ; j++) std::cout << g[i][j] << ' ';
    //     std::cout << std::endl;
    // }
    while (que.size()) {
        auto [d, v] = que.top();
        que.pop();
        if (Bigger(d, dist[v])) continue;
        for (int i = 0 ; i < n ; i++) if (Smaller(d + g[v][i], dist[i])) {
            dist[i] = d + g[v][i];
            que.push({dist[i], i});
        }
    }
    return dist[go];
}
int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(5);
    while (true) {
        std::cin >> N;
        if (N == 0) break;
        for (int i = 0 ; i < N ; i++) {
            std::cin >> NV[i] >> H[i];
            Polygon p(NV[i]);
            for (int j = 0 ; j < NV[i] ; j++) std::cin >> p[j].x() >> p[j].y();
            P[i] = std::move(p);
        }
        std::cin >> THETA >> GAMMA;
        THETA = ArcToRadian(THETA);
        GAMMA = ArcToRadian(GAMMA);
        std::cin >> START.x() >> START.y() >> GOAL.x() >> GOAL.y();
        std::cout << solve() << '\n';
    }
}
Back to top page