base_accurate
(geometry3D/accurate/base_accurate.hpp)

View this file on GitHub
Last update: 2023-05-17 22:41:14+09:00
Include: #include "geometry3D/accurate/base_accurate.hpp"

3次元幾何を整数で正確に扱うためのライブラリです。

コンストラクタ

Vec<T>

3次元の点やベクトルを表す構造体です。点の座標は T = ll,int,lib::rational などの型で保持します。

cross(外積)

Vec<T> cross(const Vec<T> &a, const Vec<T> &b)

外積 $a\times b$ を返します。

dot(内積)

T dot(const Vec<T> &a, const Vec<T> &b)

内積 $a\cdot b$ を返します。

norm(ノルム)

T norm(const Vec<T> &a)

$a$ のノルムを返します。

return a.x*a.x + a.y*a.y + a.z*a.z

Line (直線)

Line<T>

3次元上の直線をそれが通る異なる $2$ 点を保持して管理します。

intersection

int intersection(const Line<rational> &p, const Line<rational> &q)

有理数型で管理されている直線を $2$ つ受け取り、それらの関係を返します。

$p,q$ が唯一の交点を持つとき 0
$p,q$ が平行でないとき 1
$p,q$ が一致するとき 2
$p,q$ が平行であって一致しないとき 3

をそれぞれ返します。

cross_point

Vec<rational> cross_point(const Line<rational> &p, const Line<rational> &q)

有理数型で管理されている直線が唯一の交点を持つとき、その交点を返します。

assert(intersection(p,q) == 0) つまり、唯一の交点を持つことを要請します。

使用例

AtCoder301-G Worst Picture への提出

Depends on

Required by

geometry3D/accurate/line.hpp

Code

#pragma once

#include "../../template/template.hpp"
#include "../base_arbitary.hpp"

namespace lib {

template<typename T>
bool operator==(const Vec<T>& lhs, const Vec<T>& rhs) {
    return lhs.x == rhs.x && lhs.y == rhs.y && lhs.z == rhs.z;
}

template<typename T>
T dot(const Vec<T> &a, const Vec<T> &b){
    return a.x*b.x + a.y*b.y + a.z*b.z;
}

template<typename T>
Vec<T> cross(const Vec<T> &a, const Vec<T> &b){
    return Vec(a.y*b.z-a.z*b.y, a.z*b.x-a.x*b.z, a.x*b.y-a.y*b.x);
}

template<typename T>
T norm(const Vec<T> &a){
    return a.x*a.x+a.y*a.y+a.z*a.z;
}

}  // namespace lib

#line 2 "geometry3D/accurate/base_accurate.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 2 "geometry3D/base_arbitary.hpp"

#line 4 "geometry3D/base_arbitary.hpp"

namespace lib {

template<typename T>
struct Vec {
    T x, y, z;
    Vec (T _x = 0, T _y = 0, T _z = 0) : x(_x), y(_y), z(_z) {}
    Vec& operator*=(const T& a){
        x *= a;
        y *= a;
        z *= a;
        return *this;
    }
    Vec& operator/=(const T& a){
        x /= a;
        y /= a;
        z /= a;
        return *this;
    }
    Vec& operator+=(const Vec& rhs) {
        x += rhs.x;
        y += rhs.y;
        z += rhs.z;
        return *this;
    }
    Vec& operator-=(const Vec& rhs) {
        x -= rhs.x;
        y -= rhs.y;
        z -= rhs.z;
        return *this;
    }
    friend Vec operator+(const Vec& lhs, const Vec& rhs) {
        return Vec(lhs) += rhs;
    }
    friend Vec operator-(const Vec& lhs, const Vec& rhs) {
        return Vec(lhs) -= rhs;
    }
    friend Vec operator*(const Vec& lhs, const T& rhs) {
        return Vec(lhs) *= rhs;
    }
    friend Vec operator*(const T& rhs, const Vec& lhs) {
        return Vec(lhs) *= rhs;
    }
    friend Vec operator/(const Vec& lhs, const T& rhs) {
        return Vec(lhs) /= rhs;
    }
    friend std::ostream &operator<<(std::ostream &os,const Vec&r) {
        return os << "(" << r.x << "," << r.y << "," << r.z << ")"; 
    }
};

};
#line 5 "geometry3D/accurate/base_accurate.hpp"

namespace lib {

template<typename T>
bool operator==(const Vec<T>& lhs, const Vec<T>& rhs) {
    return lhs.x == rhs.x && lhs.y == rhs.y && lhs.z == rhs.z;
}

template<typename T>
T dot(const Vec<T> &a, const Vec<T> &b){
    return a.x*b.x + a.y*b.y + a.z*b.z;
}

template<typename T>
Vec<T> cross(const Vec<T> &a, const Vec<T> &b){
    return Vec(a.y*b.z-a.z*b.y, a.z*b.x-a.x*b.z, a.x*b.y-a.y*b.x);
}

template<typename T>
T norm(const Vec<T> &a){
    return a.x*a.x+a.y*a.y+a.z*a.z;
}

}  // namespace lib

base_accurate (geometry3D/accurate/base_accurate.hpp)