三角形の重心
(Geometry/triangle_center/Centroid.hpp)

View this file on GitHub
Last update: 2025-09-27 14:54:24+09:00
Include: #include "Geometry/triangle_center/Centroid.hpp"

Outline

三角形 $\mathrm{ABC}$ の重心 $\mathrm{G}$ を求める.

Theory

以下の定理がある.

三角形 $\mathrm{ABC}$ において, 線分 $\mathrm{BC}, \mathrm{CA}, \mathrm{AB}$ の中点をそれぞれ $\mathrm{L}, \mathrm{M}, \mathrm{N}$ とおく. このとき, 線分 $\mathrm{AL}, \mathrm{BM}, \mathrm{CN}$ は一点で交わる.

証明

線分 $\mathrm{AL}, \mathrm{BM}$ の交点を $\mathrm{G}$ とする. このとき, それぞれ

\[\mathrm{G} = s \mathrm{A} + (1-s) \mathrm{L} = s \mathrm{A} + (1-s) \cdot \dfrac{\mathrm{B}+\mathrm{C}}{2}\] \[\mathrm{G} = t \mathrm{B} + (1-t) \mathrm{M} = t \mathrm{B} + (1-s) \cdot \dfrac{\mathrm{C}+\mathrm{A}}{2}\]

となる $0$ 以上 $1$ 以下の整数 $s, t$ が存在する.

$\mathrm{A}$ を始点とするベクトルに変換させると,

$\mathrm{G} = \overrightarrow{\mathrm{AG}} - \overrightarrow{\mathrm{AO}}$.
$s \mathrm{A} + (1-s) \cdot \dfrac{\mathrm{B}+\mathrm{C}}{2} = -s \overrightarrow{\mathrm{AO}} + (1-s) \cdot \dfrac{\left(\overrightarrow{\mathrm{AB}} - \overrightarrow{\mathrm{AO}} \right) + \left(\overrightarrow{\mathrm{AC}} - \overrightarrow{\mathrm{AO}} \right)}{2} = \dfrac{1-s}{2} \cdot \overrightarrow{\mathrm{AB}} + \dfrac{1-s}{2} \cdot \overrightarrow{\mathrm{AC}} - \overrightarrow{\mathrm{AO}}$

である.

そのため,

\[\overrightarrow{\mathrm{AG}} = \dfrac{1-s}{2} \cdot \overrightarrow{\mathrm{AB}} + \dfrac{1-s}{2} \cdot \overrightarrow{\mathrm{AC}} \cdots (1)\]

が導ける.

同様にして,

\[\overrightarrow{\mathrm{AG}} = t \cdot \overrightarrow{\mathrm{AB}} + \dfrac{1-t}{2} \cdot \overrightarrow{\mathrm{AC}} \cdots (2)\]

も従う.

ここで, $\mathrm{A}, \mathrm{B}, \mathrm{C}$ は三角形を成す $3$ 点であるため, $\overrightarrow{\mathrm{AB}}, \overrightarrow{\mathrm{AC}}$ は一次独立である.

よって, (1), (2) における係数比較により, $s, t$ は

\[\dfrac{1-s}{2} = t, \quad \dfrac{1-s}{2} = \dfrac{1-t}{2}\]

を満たす. これを解くと,

\[s = t = \dfrac{1}{3}\]

となる.

これは, $\mathrm{G}$ は確かに線分 $\mathrm{AL}, \mathrm{BM}$ 上に存在すること. そして,

\[\mathrm{G} = s \mathrm{A} + (1-s) \cdot \dfrac{\mathrm{B}+\mathrm{C}}{2} = \dfrac{\mathrm{A} + \mathrm{B} + \mathrm{C}}{3}\]

であることを意味する.

そして,

\[G = \dfrac{\mathrm{A} + \mathrm{B} + \mathrm{C}}{3} = \dfrac{1}{3} \mathrm{C} + \dfrac{2}{3} \cdot \dfrac{\mathrm{A} + \mathrm{B}}{2} = \dfrac{1}{3} \mathrm{C} + \dfrac{2}{3} \mathrm{N}\]

であるため, $\mathrm{G}$ は線分 $\mathrm{CN}$ 上の点でもある.

以上から, 線分 $\mathrm{AL}, \mathrm{BM}, \mathrm{CN}$ は一点で交わる.

$\square$

この定理における, 点 $\mathrm{G}$ を三角形 $\mathrm{ABC}$ の重心という.

template<typename R>
Point<R> Centroid(const Triangle<R> &T)

三角形 $\mathrm{T}$ の重心を求める.

Depends on

Code

#pragma once

#include"../object/Triangle.hpp"

namespace geometry {
    template<typename R>
    Point<R> Centroid(const Triangle<R> &T) { return T.balance(1, 1, 1); }
}

#line 2 "Geometry/triangle_center/Centroid.hpp"

#line 2 "Geometry/object/Triangle.hpp"

#line 2 "Geometry/object/Point.hpp"

#line 2 "Geometry/base.hpp"

#line 2 "template/template.hpp"

using namespace std;

// intrinstic
#include <immintrin.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfenv>
#include <cfloat>
#include <chrono>
#include <cinttypes>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <ios>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <streambuf>
#include <string>
#include <tuple>
#include <type_traits>
#include <typeinfo>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

// utility
#line 2 "template/utility.hpp"

using ll = long long;

// a ← max(a, b) を実行する. a が更新されたら, 返り値が true.
template<typename T, typename U>
inline bool chmax(T &a, const U b){
    return (a < b ? a = b, 1: 0);
}

// a ← min(a, b) を実行する. a が更新されたら, 返り値が true.
template<typename T, typename U>
inline bool chmin(T &a, const U b){
    return (a > b ? a = b, 1: 0);
}
#line 59 "template/template.hpp"

// math
#line 2 "template/math.hpp"

// 除算に関する関数

// floor(x / y) を求める.
template<typename T, typename U>
T div_floor(T x, U y){ return (x > 0 ? x / y: (x - y + 1) / y); }

// ceil(x / y) を求める.
template<typename T, typename U>
T div_ceil(T x, U y){ return (x > 0 ? (x + y - 1) / y: x / y) ;}

// x を y で割った余りを求める.
template<typename T, typename U>
T mod(T x, U y){
    T q = div_floor(x, y);
    return x - q * y ;
}

// x を y で割った商と余りを求める.
template<typename T, typename U>
pair<T, T> divmod(T x, U y){
    T q = div_floor(x, y);
    return {q, x - q * y};
}

// 四捨五入を求める.
template<typename T, typename U>
T round(T x, U y){
    T q, r;
    tie (q, r) = divmod(x, y);
    return (r >= div_ceil(y, 2)) ? q + 1 : q;
}

// 指数に関する関数

// x の y 乗を求める.
ll intpow(ll x, ll y){
    ll a = 1;
    while (y){
        if (y & 1) { a *= x; }
        x *= x;
        y >>= 1;
    }
    return a;
}

// x の y 乗を z で割った余りを求める.
ll modpow(ll x, ll y, ll z){
    ll a = 1;
    while (y){
        if (y & 1) { (a *= x) %= z; }
        (x *= x) %= z;
        y >>= 1;
    }
    return a;
}

// x の y 乗を z で割った余りを求める.
template<typename T, typename U>
T modpow(T x, U y, T z) {
    T a = 1;
    while (y) {
        if (y & 1) { (a *= x) %= z; }

        (x *= x) %= z;
        y >>= 1;
    }

    return a;
}

// vector の要素の総和を求める.
ll sum(vector<ll> &X){
    ll y = 0;
    for (auto &&x: X) { y+=x; }
    return y;
}

// vector の要素の総和を求める.
template<typename T>
T sum(vector<T> &X){
    T y = T(0);
    for (auto &&x: X) { y += x; }
    return y;
}

// a x + b y = gcd(a, b) を満たす整数の組 (a, b) に対して, (x, y, gcd(a, b)) を求める.
tuple<ll, ll, ll> Extended_Euclid(ll a, ll b) {
    ll s = 1, t = 0, u = 0, v = 1;
    while (b) {
        ll q;
        tie(q, a, b) = make_tuple(div_floor(a, b), b, mod(a, b));
        tie(s, t) = make_pair(t, s - q * t);
        tie(u, v) = make_pair(v, u - q * v);
    }

    return make_tuple(s, u, a);
}

// floor(sqrt(N)) を求める (N < 0 のときは, 0 とする).
ll isqrt(const ll &N) { 
    if (N <= 0) { return 0; }

    ll x = sqrt(N);
    while ((x + 1) * (x + 1) <= N) { x++; }
    while (x * x > N) { x--; }

    return x;
}

// floor(sqrt(N)) を求める (N < 0 のときは, 0 とする).
ll floor_sqrt(const ll &N) { return isqrt(N); }

// ceil(sqrt(N)) を求める (N < 0 のときは, 0 とする).
ll ceil_sqrt(const ll &N) {
    ll x = isqrt(N);
    return x * x == N ? x : x + 1;
}
#line 62 "template/template.hpp"

// inout
#line 1 "template/inout.hpp"
// 入出力
template<class... T>
void input(T&... a){ (cin >> ... >> a); }

void print(){ cout << "\n"; }

template<class T, class... Ts>
void print(const T& a, const Ts&... b){
    cout << a;
    (cout << ... << (cout << " ", b));
    cout << "\n";
}

template<typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &P){
    is >> P.first >> P.second;
    return is;
}

template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &P){
    os << P.first << " " << P.second;
    return os;
}

template<typename T>
vector<T> vector_input(int N, int index){
    vector<T> X(N+index);
    for (int i=index; i<index+N; i++) cin >> X[i];
    return X;
}

template<typename T>
istream &operator>>(istream &is, vector<T> &X){
    for (auto &x: X) { is >> x; }
    return is;
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &X){
    int s = (int)X.size();
    for (int i = 0; i < s; i++) { os << (i ? " " : "") << X[i]; }
    return os;
}

template<typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &S){
    int i = 0;
    for (T a: S) {os << (i ? " ": "") << a; i++;}
    return os;
}

template<typename T>
ostream &operator<<(ostream &os, const set<T> &S){
    int i = 0;
    for (T a: S) { os << (i ? " ": "") << a; i++; }
    return os;
}

template<typename T>
ostream &operator<<(ostream &os, const unordered_multiset<T> &S){
    int i = 0;
    for (T a: S) { os << (i ? " ": "") << a; i++; }
    return os;
}

template<typename T>
ostream &operator<<(ostream &os, const multiset<T> &S){
    int i = 0;
    for (T a: S) { os << (i ? " ": "") << a; i++; }
    return os;
}
#line 65 "template/template.hpp"

// macro
#line 2 "template/macro.hpp"

// マクロの定義
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if
#define unless(cond) if (!(cond))
#define until(cond) while (!(cond))
#define loop while (true)

// オーバーロードマクロ
#define overload2(_1, _2, name, ...) name
#define overload3(_1, _2, _3, name, ...) name
#define overload4(_1, _2, _3, _4, name, ...) name
#define overload5(_1, _2, _3, _4, _5, name, ...) name

// 繰り返し系
#define rep1(n) for (ll i = 0; i < n; i++)
#define rep2(i, n) for (ll i = 0; i < n; i++)
#define rep3(i, a, b) for (ll i = a; i < b; i++)
#define rep4(i, a, b, c) for (ll i = a; i < b; i += c)
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)

#define foreach1(x, a) for (auto &&x: a)
#define foreach2(x, y, a) for (auto &&[x, y]: a)
#define foreach3(x, y, z, a) for (auto &&[x, y, z]: a)
#define foreach4(x, y, z, w, a) for (auto &&[x, y, z, w]: a)
#define foreach(...) overload5(__VA_ARGS__, foreach4, foreach3, foreach2, foreach1)(__VA_ARGS__)
#line 68 "template/template.hpp"

// bitop
#line 2 "template/bitop.hpp"

// 非負整数 x の bit legnth を求める.
ll bit_length(ll x) {
    if (x == 0) { return 0; }
    return (sizeof(long) * CHAR_BIT) - __builtin_clzll(x);
}

// 非負整数 x の popcount を求める.
ll popcount(ll x) { return __builtin_popcountll(x); }

// 正の整数 x に対して, floor(log2(x)) を求める.
ll floor_log2(ll x) { return bit_length(x) - 1; }

// 正の整数 x に対して, ceil(log2(x)) を求める.
ll ceil_log2(ll x) { return bit_length(x - 1); }

// x の第 k ビットを取得する
int get_bit(ll x, int k) { return (x >> k) & 1; }

// x のビット列を取得する.
// k はビット列の長さとする.
vector<int> get_bits(ll x, int k) {
    vector<int> bits(k);
    rep(i, k) {
        bits[i] = x & 1;
        x >>= 1;
    }

    return bits;
}

// x のビット列を取得する.
vector<int> get_bits(ll x) { return get_bits(x, bit_length(x)); }
#line 4 "Geometry/base.hpp"

namespace geometry {
    using Real = double long;
    const Real epsilon = 1e-9;
    const Real pi = acos(static_cast<Real>(-1));

    enum class Inclusion { OUT = -1, ON = 0, IN = 1 };
    enum class Direction_Relation { PARALLEL = 1, ORTHOGONAL = -1, CROSS = 0}; 

    inline int sign(const Real &r) { return r <= -epsilon ? -1 : r >= epsilon ? 1: 0; }
    inline int equal(const Real &a, const Real &b) { return sign(a - b) == 0; }
    inline int compare(const Real &a, const Real &b) { return sign(b - a); }

    inline int sign(const ll &r) { return r < 0 ? -1 : r > 0 ? 1 : 0; }
    inline int equal(const ll &a, const ll &b) { return sign(a - b) == 0; }
    inline int compare(const ll &a, const ll &b) { return sign(b - a); }

    inline int sign(const int &r) { return r < 0 ? -1 : r > 0 ? 1 : 0; }
    inline int equal(const int &a, const int &b) { return sign(a - b) == 0; }
    inline int compare(const int &a, const int &b) { return sign(b - a); }
};
#line 4 "Geometry/object/Point.hpp"

namespace geometry {
    template<typename R>
    class Point {
        public:
        R x, y;

        public:
        Point(): x(0), y(0) {}
        Point(R _x, R _y): x(_x), y(_y) {}

        // 加法
        Point& operator+=(const Point &B){
            x += B.x;
            y += B.y;
            return *this;
        }

        friend Point operator+(const Point &P, const Point &Q) { return Point(P) += Q; }

        // 減法
        Point& operator-=(const Point &B){
            x -= B.x;
            y -= B.y;
            return *this;
        }

        friend Point operator-(const Point &P, const Point &Q) { return Point(P) -= Q; }

        // スカラー倍
        Point& operator*=(const R &a){
            x *= a;
            y *= a;
            return *this;
        }

        friend Point operator*(const Point &P, const R &a) { return Point(P) *= a; }
        friend Point operator*(const R &a, const Point &P) { return Point(P) *= a; }

        Point& operator/=(const R &a){
            x /= a;
            y /= a;
            return *this;
        }

        friend Point operator/(const Point &P, const R &a) { return Point(P) /= a; }

        Point& operator*=(const Point &P){
            R x1 = P.x * x - P.y * y, y1 = P.y * x + P.x * y;
            x = x1;
            y = y1;
            return *this;
        }

        friend Point operator*(const Point &P, const Point<R> &Q) { return Point(P) *= Q; }

        friend istream& operator>>(istream &is, Point &P) {
            R a, b;
            is >> a >> b;
            P = Point(a, b);
            return is;
        }

        friend ostream& operator<<(ostream &os, const Point &P) {
            return os << P.x << " " << P.y;
        }

        inline R norm_2() const { return x * x + y * y; }
        inline double norm() const { return sqrt(norm_2()); }
        inline R dot(const Point B) const { return x * B.x + y * B.y; }
        inline R det(const Point B) const { return x * B.y - y * B.x; }

        inline Point<R> normalize() const { return *this / norm(); }
        inline Point<R> normal() const { return Point(-y, x); }

        inline Point<Real> rotate(double theta) const {
            Real alpha = sin(theta), beta = cos(theta);
            Real s = beta * x - alpha * y, t = alpha * x + beta * y;
            return Point(s, t);
        }
    };

    template<typename R>
    bool compare_x(const Point<R> &A, const Point<R> &B) { return equal(A.x, B.x) ? A.y < B.y : A.x < B.x; }

    template<typename R>
    bool compare_y(const Point<R> &A, const Point<R> &B) { return equal(A.y, B.y) ? A.x < B.x : A.y < B.y; }

    template<typename R>
    inline bool operator==(const Point<R> &A, const Point<R> &B) { return equal(A.x, B.x) && equal(A.y, B.y); }

    template<typename R>
    inline bool operator!=(const Point<R> &A, const Point<R> &B) { return !(A == B); }

    template<typename R>
    inline R dot(const Point<R> &A, const Point<R> &B) { return A.x * B.x + A.y * B.y; }

    template<typename R>
    inline R cross(const Point<R> &A, const Point<R> &B) { return A.x * B.y - A.y * B.x; }

    template<typename R>
    inline R norm_2(const Point<R> &P) { return dot(P, P); }

    template<typename R>
    inline double norm(const Point<R> &P) { return sqrt(norm_2(P)); }

    template<typename R>
    inline Real arg(const Point<R> &P) { return atan2(P.y, P.x); }
}
#line 4 "Geometry/object/Triangle.hpp"

namespace geometry {
    template<typename R>
    class Triangle {
        public:
        Point<R> A, B, C;

        public:
        Triangle() = default;
        Triangle(const Point<R> a, const Point<R> b, const Point<R> c): A(a), B(b), C(c) {}

        // 辺 BC, 辺 CA, 辺 AB の長さを出力する.
        tuple<double, double, double> edges() const {
            return make_tuple(norm(C - B), norm(A - C), norm(B - A));
        }

        // [PBC] : [PCA] : [PAB] = alpha : beta : gamma を満たす点 P を求める.
        Point<R> balance(const R &alpha, const R &beta, const R &gamma) const {
            return (alpha * A + beta * B + gamma * C) / (alpha + beta + gamma);
        }
    };

    template<typename R>
    R Area(const Triangle<R> &T) {
        auto X = cross(T.B - T.A, T.C - T.A);
        return sign(X) >= 0 ? X / 2 : -X / 2;
    }
}
#line 4 "Geometry/triangle_center/Centroid.hpp"

namespace geometry {
    template<typename R>
    Point<R> Centroid(const Triangle<R> &T) { return T.balance(1, 1, 1); }
}

library_for_cpp

三角形の重心
(Geometry/triangle_center/Centroid.hpp)

Outline

Theory

証明

Contents

Depends on

Code

三角形の重心 (Geometry/triangle_center/Centroid.hpp)

Outline

Theory

証明

Contents

Depends on

Code

三角形の重心
(Geometry/triangle_center/Centroid.hpp)