AOJ1053 Accelerated Railgun
(Test/AOJ/1053.test.cpp)

• View this file on GitHub
• Last update: 2023-11-20 11:32:11+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/1053

愚直にプロジェクトタイルの移動をシミュレーションする。制約より、高々25回の反射でプロジェクトタイルの移動は終了する。

鏡面での直線の反射を考える時の典型として「直線を反射するのではなく、他の物体を鏡面のReflectionに移動する(反射したとみなす)」

• 偏角の扱いに困ることが無い

参考: プログラミングコンテストにおける計算幾何入門

Depends on

• Src/GeometryR2/Angle.hpp
• Src/GeometryR2/Circle.hpp
• Src/GeometryR2/CrossPoint/CircleAndLine.hpp
• Src/GeometryR2/Distance/LineAndPoint.hpp
• Src/GeometryR2/Distance/PointAndPoint.hpp
• Src/GeometryR2/Distance/PointAndSegment.hpp
• Src/GeometryR2/Intersect/CircleAndLine.hpp
• Src/GeometryR2/Line.hpp
• Src/GeometryR2/Point.hpp
• Src/GeometryR2/Projection.hpp
• Src/GeometryR2/Real.hpp
• Src/GeometryR2/Reflection.hpp
• Src/GeometryR2/Relation.hpp
• Src/GeometryR2/Segment.hpp
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Code

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

#include "../../Src/GeometryR2/Real.hpp"
#include "../../Src/GeometryR2/Segment.hpp"
#include "../../Src/GeometryR2/Point.hpp"
#include "../../Src/GeometryR2/Circle.hpp"
#include "../../Src/GeometryR2/Distance/PointAndPoint.hpp"
#include "../../Src/GeometryR2/Distance/PointAndSegment.hpp"
#include "../../Src/GeometryR2/CrossPoint/CircleAndLine.hpp"
#include "../../Src/GeometryR2/Reflection.hpp"

#include <algorithm>
#include <iostream>
#include <iomanip>

bool solve() {
    using namespace zawa::geometryR2;
    Real d; std::cin >> d;
    if (Zero(d)) return false;
    Point p; std::cin >> p;
    Vector v; std::cin >> v;
    v.normalize();
    Circle R{Point{0, 0}, 1};

    auto getCrossPoint{[&](const Line& l) -> Point {
        auto cp{CrossPoint(R, l)};
        if (cp.first == p) return cp.second;
        if (cp.second == p) return cp.first;
        if (Positive(Dot(v, cp.first - p))) return cp.first;
        return cp.second;
    }};

    auto getEnd{[&](const Point& cp) -> Point {
        Real len{std::min(Distance(cp, p), d)};
        return p + v * len;
    }};

    auto reflect{[&](const Point& collision) -> void {
        Vector dir{Vector(collision - R.center()).rotatedByArc(90)};
        Line ref{collision, collision - dir};
        R.center() = Reflection(R.center(), ref);
    }};

    Real ans{};

    while (Positive(d)) {
        Line line{p, p + v};
        auto collision{getCrossPoint(line)};
        auto end{getEnd(collision)};
        if (PointOnSegment(R.center(), Segment{p, end})) {
            Real dist{Distance(Point{0, 0}, p)};
            ans += dist;
            break;
        }
        d -= Distance(end, p);
        ans += Distance(end, p);
        reflect(end);
        p = end;
    }

    if (!Zero(d)) {
        std::cout << ans << '\n';
    }
    else {
        std::cout << "impossible\n";
    }

    return true;
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(7);

    for (int i{} ; solve() ; i++) {

    }
}

#line 1 "Test/AOJ/1053.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/1053"
#define ERROR 0.000001

#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 2 "Src/GeometryR2/Segment.hpp"

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

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

#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 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 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 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"

#include <algorithm>
#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/Circle.hpp"

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

#line 9 "Src/GeometryR2/Circle.hpp"
#include <utility>

namespace zawa {

namespace geometryR2 {

class Circle {
private:
    Point center_{};
    Real radius_{};
public:
    /* constructor */
    Circle() = default;
    Circle(const Point& center, Real radius) : center_{center}, radius_{radius} {
        assert(!Negative(radius));
    }
    Circle(Real x, Real y, Real r) : center_{x, y}, radius_{r} {
        assert(!Negative(r));
    }

    /* getter setter */
    const Point& center() const {
        return center_;
    }
    Point& center() {
        return center_;
    }
    Real radius() const {
        return radius_;
    }
    Real& radius() {
        return radius_;
    }

    /* operator */
    friend bool operator==(const Circle& lhs, const Circle& rhs) {
        return lhs.center() == rhs.center() and Equal(lhs.radius(), rhs.radius());
    }
    friend bool operator!=(const Circle& lhs, const Circle& rhs) {
        return lhs.center() != rhs.center() or !Equal(lhs.radius(), rhs.radius());
    }

    /* friend function */
    friend u32 NumberCommonTangent(const Circle& c0, const Circle& c1) {
        Real dist{DistanceSquare(c0.center(), c1.center())};
        Real down{Square(Abs(c0.radius() - c1.radius()))};
        if (Smaller(dist, down)) return 0;
        if (Equal(dist, down)) return 1;
        Real up{Square(c0.radius() + c1.radius())};
        if (Smaller(dist, up)) return 2;
        if (Equal(dist, up)) return 3;
        return 4;
    }
};

} // 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 2 "Src/GeometryR2/CrossPoint/CircleAndLine.hpp"

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

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

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

namespace zawa {

namespace geometryR2 {

class Line {
private:
    Point p0_{}, p1_{};
public:
    /* constructor */
    Line() = default;
    Line(const Point& p0, const Point& p1) : p0_{p0}, p1_{p1} {}
    // y = ax + b 
    Line(Real a, Real b) : p0_{static_cast<Real>(0), b}, p1_{static_cast<Real>(1), a + b} {}

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

    /* operator */
    friend bool operator==(const Line& l0, const Line& l1) {
        return Zero(Cross(l0.p1() - l0.p0(), l1.p1() - l1.p0())) and Zero(Cross(l0.p1() - l0.p0(), l1.p1() - l0.p0()));
    }
    friend bool operator!=(const Line& l0, const Line& l1) {
        return !Zero(Cross(l0.p1() - l0.p0(), l1.p1() - l1.p0())) or !Zero(Cross(l0.p1() - l0.p0(), l1.p1() - l0.p0()));
    }

    /* member function */
    bool valid() const {
        return p0_ != p1_;
    }
    Vector slope() const {
        assert(valid());
        return Vector{p1() - p0()}.normalized();
    }
};

} // namespace geometryR2

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

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

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

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

namespace zawa {

namespace geometryR2 {

Real Distance(const Line& l, const Point& p) {
    assert(l.valid());
    return Abs(Cross(p - l.p0(), l.p1() - l.p0())) / Distance(l.p1(), l.p0());
}

bool PointOnLine(const Line& l, const Point& p) {
    assert(l.valid());
    return Zero(Distance(l, p));
}

} // namespace geometryR2

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

#line 8 "Src/GeometryR2/Intersect/CircleAndLine.hpp"

namespace zawa {
    
namespace geometryR2 {

bool Intersect(const Circle& c, const Line& l) {
    assert(l.valid());
    return !Bigger(Distance(l, c.center()), c.radius());
}
    
} // namespace geometryR2

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

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

#line 8 "Src/GeometryR2/Projection.hpp"

namespace zawa {

namespace geometryR2 {

Point Projection(const Point& point, const Line& line) {
    assert(line.valid());
    Real coeff{Dot(line.p1() - line.p0(), point - line.p0()) / DistanceSquare(line.p0(), line.p1())};
    return coeff * line.p1() + (static_cast<Real>(1) - coeff) * line.p0();
}

} // namespace geometryR2

} // namespace zawa
#line 9 "Src/GeometryR2/CrossPoint/CircleAndLine.hpp"

#line 12 "Src/GeometryR2/CrossPoint/CircleAndLine.hpp"

namespace zawa {

namespace geometryR2 {

std::pair<Point, Point> CrossPoint(const Circle& c, const Line& l) {
    assert(l.valid());
    assert(Intersect(c, l));
    Point pr{Projection(c.center(), l)};
    Vector e{(l.p1() - l.p0()) / Distance(l.p0(), l.p1())};
    Real len{Sqrt(Square(c.radius()) - DistanceSquare(pr, c.center()))};
    return std::pair<Point, Point>{
        pr + e * len,
        pr - e * len
    };
}

} // namespace geometryR2

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

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

namespace zawa {

namespace geometryR2 {

Point Reflection(const Point& point, const Line& line) {
    assert(line.valid());
    return -point + static_cast<Real>(2) * Projection(point, line);
}

} // namespace geometryR2

} // namespace zawa
#line 12 "Test/AOJ/1053.test.cpp"

#line 15 "Test/AOJ/1053.test.cpp"
#include <iomanip>

bool solve() {
    using namespace zawa::geometryR2;
    Real d; std::cin >> d;
    if (Zero(d)) return false;
    Point p; std::cin >> p;
    Vector v; std::cin >> v;
    v.normalize();
    Circle R{Point{0, 0}, 1};

    auto getCrossPoint{[&](const Line& l) -> Point {
        auto cp{CrossPoint(R, l)};
        if (cp.first == p) return cp.second;
        if (cp.second == p) return cp.first;
        if (Positive(Dot(v, cp.first - p))) return cp.first;
        return cp.second;
    }};

    auto getEnd{[&](const Point& cp) -> Point {
        Real len{std::min(Distance(cp, p), d)};
        return p + v * len;
    }};

    auto reflect{[&](const Point& collision) -> void {
        Vector dir{Vector(collision - R.center()).rotatedByArc(90)};
        Line ref{collision, collision - dir};
        R.center() = Reflection(R.center(), ref);
    }};

    Real ans{};

    while (Positive(d)) {
        Line line{p, p + v};
        auto collision{getCrossPoint(line)};
        auto end{getEnd(collision)};
        if (PointOnSegment(R.center(), Segment{p, end})) {
            Real dist{Distance(Point{0, 0}, p)};
            ans += dist;
            break;
        }
        d -= Distance(end, p);
        ans += Distance(end, p);
        reflect(end);
        p = end;
    }

    if (!Zero(d)) {
        std::cout << ans << '\n';
    }
    else {
        std::cout << "impossible\n";
    }

    return true;
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(7);

    for (int i{} ; solve() ; i++) {

    }
}

Back to top page