Test/AOJ/2641.test.cpp

• View this file on GitHub
• Last update: 2025-05-21 23:28:51+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/2641

Depends on

• Src/GeometryR3/Point.hpp
• Src/GeometryR3/Segment.hpp
• Src/GeometryR3/Sphere.hpp
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2641"

#include "../../Src/GeometryR3/Segment.hpp"
#include "../../Src/GeometryR3/Sphere.hpp"
using namespace zawa::geometryR3;

#include <iostream>

int N, Q;
long long L[50];
Sphere<long double> B[50];
int main() {
    std::cin >> N >> Q;
    for (int i = 0 ; i < N ; i++) {
        std::cin >> B[i].center() >> B[i].radius() >> L[i];
    }
    while (Q--) {
        Segment<long double> s;
        std::cin >> s.p() >> s.q();
        long long ans = 0;
        for (int i = 0 ; i < N ; i++) {
            const long double d = Distance(B[i].center(), s);
            if (B[i].radius() - d > -1e-8) ans += L[i];
        }
        std::cout << ans << '\n';
    }
}

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

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

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

#include <array>
#include <cassert>
#include <cmath>
#include <concepts>
#include <iostream>
#include <utility>

#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 11 "Src/GeometryR3/Point.hpp"

namespace zawa {

namespace geometryR3 {

template <std::floating_point T>
class Point {
public:

    Point() = default;

    Point(T x, T y, T z) : m_p{x, y, z} {}

    explicit Point(const std::array<T, 3>& p) : m_p{p} {}

    explicit Point(std::array<T, 3>&& p) : m_p{std::move(p)} {}

    const T& x() const {
        return m_p[0];
    }

    T& x() {
        return m_p[0];
    }

    const T& y() const {
        return m_p[1];
    }

    T& y() {
        return m_p[1];
    }

    const T& z() const {
        return m_p[2];
    }

    T& z() {
        return m_p[2];
    }

    const T& operator[](usize i) const {
        assert(i < 3);
        return m_p[i];
    }

    T& operator[](usize i) {
        assert(i < 3);
        return m_p[i];
    }

    Point<T>& operator+=(const Point<T>& p) {
        m_p[0] += p[0];
        m_p[1] += p[1];
        m_p[2] += p[2];
        return *this;
    }

    Point<T>& operator-=(const Point<T>& p) {
        m_p[0] -= p[0];
        m_p[1] -= p[1];
        m_p[2] -= p[2];
        return *this;
    }

    Point<T>& operator*=(T k) {
        m_p[0] *= k;
        m_p[1] *= k;
        m_p[2] *= k;
        return *this;
    }

    Point<T>& operator/=(T k) {
        m_p[0] /= k;
        m_p[1] /= k;
        m_p[2] /= k;
        return *this;
    }

    T normSquare() const {
        return m_p[0]*m_p[0] + m_p[1]*m_p[1] + m_p[2]*m_p[2];
    }

    T norm() const {
        return sqrtl(normSquare());
    }

    Point<T> normalized() const {
        return Point<T>{*this} /= norm();
    }

    // ロドリゲスの回転公式 https://manabitimes.jp/math/2649
    Point<T> rotated(const Point<T>& axis, T theta) const {
        const T cosT = cosl(theta), sinT = sinl(theta);
        const Point<T> cp{*this};
        return cosT * cp + (1 - cosT) * DotProduct(axis, cp) * axis + sinT * CrossProduct(axis, cp);
    }

private:

    std::array<T, 3> m_p{T{0}, T{0}, T{0}};

};

template <std::floating_point T>
Point<T> operator+(const Point<T>& lhs, const Point<T>& rhs) {
    return Point<T>{lhs} += rhs;
}

template <std::floating_point T>
Point<T> operator-(const Point<T>& lhs, const Point<T>& rhs) {
    return Point<T>{lhs} -= rhs;
}

template <std::floating_point T>
Point<T> operator*(const T k, const Point<T>& p) {
    return Point<T>{p} *= k;
}

template <std::floating_point T>
std::ostream& operator<<(std::ostream& os, const Point<T>& p) {
    os << '(' << p[0] << ',' << p[1] << ',' << p[2] << ')';
    return os;
}

template <std::floating_point T>
std::istream& operator>>(std::istream& is, Point<T>& p) {
    is >> p[0] >> p[1] >> p[2];
    return is;
}

template <std::floating_point T>
T DistanceSquare(const Point<T>& lhs, const Point<T>& rhs) {
    return Point{lhs - rhs}.normSquare();
}

template <std::floating_point T>
T Distance(const Point<T>& lhs, const Point<T>& rhs) {
    return sqrtl(DistanceSquare(lhs, rhs));
}

template <std::floating_point T>
T DotProduct(const Point<T>& lhs, const Point<T>& rhs) {
    return lhs[0]*rhs[0] + lhs[1]*rhs[1] + lhs[2]*rhs[2];
}

template <std::floating_point T>
Point<T> CrossProduct(const Point<T>& lhs, const Point<T>& rhs) {
    return {
        lhs[1]*rhs[2]-lhs[2]*rhs[1],
        lhs[2]*rhs[0]-lhs[0]*rhs[2],
        lhs[0]*rhs[1]-lhs[1]*rhs[0],
    };
}

template <std::floating_point T>
using Vector = Point<T>;

} // namespace geometryR3

} // namespace zawa
#line 4 "Src/GeometryR3/Segment.hpp"

#include <algorithm>
#line 7 "Src/GeometryR3/Segment.hpp"

namespace zawa {

namespace geometryR3 {

template <std::floating_point T>
class Segment {
public:
    
    Segment() = default;

    Segment(const Point<T>& p, const Point<T>& q) : m_p{p}, m_q{q} {}

    Segment(Point<T>&& p, Point<T>&& q) : m_p{std::move(p)}, m_q{std::move(q)} {}

    const Point<T>& p() const {
        return m_p;
    }

    Point<T>& p() {
        return m_p;
    }

    const Point<T>& q() const {
        return m_q;
    }

    Point<T>& q() {
        return m_q;
    }

    Vector<T> direction() const {
        return m_q - m_p;
    }

    Vector<T> unitDirection() const {
        return Vector<T>{m_q - m_p}.normalized();
    }

    Point<T> dividingPoint(T ratio) const {
        return m_p + ratio * direction();
    }

private:

    Point<T> m_p{}, m_q{};
};

template <std::floating_point T>
T Distance(const Point<T>& p, const Segment<T>& s) {
    const Vector<T> d = s.direction();
    const T k = std::clamp(DotProduct(d, p - s.p()) / d.normSquare(), T{0}, T{1});
    return Distance(s.dividingPoint(k), p);
}

} // namespace geometryR3

} // namespace zawa
#line 2 "Src/GeometryR3/Sphere.hpp"

#line 4 "Src/GeometryR3/Sphere.hpp"

namespace zawa {

namespace geometryR3 {

template <std::floating_point T>
class Sphere {
public:

    Sphere() = default;

    Sphere(const Point<T>& c, T r) : m_c{c}, m_r{r} {}

    const Point<T>& center() const {
        return m_c;
    }

    Point<T>& center() {
        return m_c;
    }

    const T& radius() const {
        return m_r;
    }

    T& radius() {
        return m_r;
    }

private:

    Point<T> m_c{};

    T m_r{0};
};

} // namespace geometryR3

} // namespace zawa
#line 5 "Test/AOJ/2641.test.cpp"
using namespace zawa::geometryR3;

#line 8 "Test/AOJ/2641.test.cpp"

int N, Q;
long long L[50];
Sphere<long double> B[50];
int main() {
    std::cin >> N >> Q;
    for (int i = 0 ; i < N ; i++) {
        std::cin >> B[i].center() >> B[i].radius() >> L[i];
    }
    while (Q--) {
        Segment<long double> s;
        std::cin >> s.p() >> s.q();
        long long ans = 0;
        for (int i = 0 ; i < N ; i++) {
            const long double d = Distance(B[i].center(), s);
            if (B[i].radius() - d > -1e-8) ans += L[i];
        }
        std::cout << ans << '\n';
    }
}

Back to top page