コンテンツにスキップ

幾何

タグ「幾何」の記事 4 件

多角形のモーメントとは何か

shogo-library の多角形のライブラリには、PolygonMoment という型と polygon_edge_moment という関数があります。どちらも「面積と一次モーメント」を扱うものですが、モーメントという言葉はなじみが薄いと思います。この記事では、モーメントとは何か、なぜ重心を求めるのに便利なのか、ライブラリでは何ができるのかを説明します。

数直線上に、重さ m1,m2,…,mnm_1, m_2, \dots, m_n のおもりが位置 x1,x2,…,xnx_1, x_2, \dots, x_n に置かれているとします。このとき

  • 零次モーメント:M0=∑imiM_0 = \sum_i m_i(重さの合計)
  • 一次モーメント:M1=∑imixiM_1 = \sum_i m_i x_i(重さ × 位置の合計)
  • 二次モーメント:M2=∑imixi2M_2 = \sum_i m_i x_i^2(重さ × 位置の 2 乗の合計)

をモーメントと呼びます。kk 次モーメントは「重さ × 位置の kk 乗」の合計です。

重心(重さの平均位置)は g=M1/M0g = M_1 / M_0 です。一次モーメントを零次モーメントで割ると重心になる、というのがこの記事でいちばん大事な式です。

名前の由来はてこです。位置 cc を支点にすると、おもり ii が回そうとする強さ(力のモーメント)は mi(xi−c)m_i (x_i - c) で、合計は M1−cM0M_1 - c M_0 です。これが 00 になる、つまり釣り合う支点が c=M1/M0c = M_1 / M_0、すなわち重心です。

平面の図形 DD では、おもりの代わりに面積を重さと考え、和を積分に置き換えます。

S=∬D1 dA,Mx=∬Dx dA,My=∬Dy dAS = \iint_D 1 \, dA, \qquad M_x = \iint_D x \, dA, \qquad M_y = \iint_D y \, dA

SS は面積(零次モーメント)、(Mx,My)(M_x, M_y) は一次モーメントです。図形の重心は

(gx,gy)=(MxS,MyS)(g_x, g_y) = \left( \frac{M_x}{S}, \frac{M_y}{S} \right)

です。言いかえると、一次モーメントは「面積 × 重心」です:(Mx,My)=S⋅(gx,gy)(M_x, M_y) = S \cdot (g_x, g_y)。

モーメントは足せる、重心は足せない

Section titled “モーメントは足せる、重心は足せない”

モーメントが便利なのは、図形を分割したとき、各部分のモーメントを足すと全体のモーメントになることです。積分の範囲を分けているだけなので当然です。面積が足せるのと同じ理由で、一次モーメントも足せます。

一方、重心はそのままでは足せません。図形 AA と BB をくっつけた図形の重心は、AA の重心と BB の重心の平均ではなく、面積で重みを付けた平均

g=SAgA+SBgBSA+SBg = \frac{S_A g_A + S_B g_B}{S_A + S_B}

です。分子は一次モーメントの和、分母は面積の和なので、これは「モーメントを足してから割る」と言っているだけです。

例として、L 字形の図形 (0,0),(2,0),(2,1),(1,1),(1,2),(0,2)(0,0), (2,0), (2,1), (1,1), (1,2), (0,2) の重心を求めます。

  • 下の長方形 [0,2]×[0,1][0,2] \times [0,1]:S=2S = 2、重心 (1,0.5)(1, 0.5)、一次モーメント (2,1)(2, 1)
  • 左上の長方形 [0,1]×[1,2][0,1] \times [1,2]:S=1S = 1、重心 (0.5,1.5)(0.5, 1.5)、一次モーメント (0.5,1.5)(0.5, 1.5)

足すと S=3S = 3、一次モーメント (2.5,2.5)(2.5, 2.5) なので、重心は (2.5/3,2.5/3)=(5/6,5/6)(2.5/3, 2.5/3) = (5/6, 5/6) です。

引き算もできます。穴の開いた図形のモーメントは「外側のモーメント − 穴のモーメント」です。このように足し算と引き算ができることが、あとで累積和に載せるときに効いてきます。

多角形のモーメントを辺ごとに分解する

Section titled “多角形のモーメントを辺ごとに分解する”

三角形 a,b,ca, b, c の面積は外積で S=12(b−a)×(c−a)S = \frac{1}{2} (b - a) \times (c - a)、重心は 3 頂点の平均 a+b+c3\frac{a + b + c}{3} です。したがって一次モーメントは

S⋅a+b+c3S \cdot \frac{a + b + c}{3}

です。

原点を頂点にした三角形に分ける

Section titled “原点を頂点にした三角形に分ける”

反時計回りの多角形 p0,p1,…,pn−1p_0, p_1, \dots, p_{n-1} を、辺 pi→pi+1p_i \to p_{i+1} ごとに原点 OO と結んだ三角形 O,pi,pi+1O, p_i, p_{i+1} に分けます(pn=p0p_n = p_0)。この三角形の符号付き面積は 12 pi×pi+1\frac{1}{2} \, p_i \times p_{i+1} で、OO から見て反時計回りなら正、時計回りなら負です。

O p₀ p₁ p₂ p₃
青は正(反時計回り)の三角形、赤は負(時計回り)の三角形。太線が多角形。

図では Op0p1O p_0 p_1, Op1p2O p_1 p_2, Op2p3O p_2 p_3 の 3 つが正で、これらを合わせると多角形よりはみ出します。はみ出した部分はちょうど負の三角形 Op3p0O p_3 p_0 と重なり、打ち消されます。凹多角形でも、原点が多角形の外にあっても同じことが起き、各点は「多角形の内部なら合計 1 回、外部なら合計 0 回」数えられます(正確には、その点のまわりを多角形が何周するか、つまり回転数の回数だけ数えられます)。

面積だけでなく一次モーメントも積分なので、同じように符号付きで足せば打ち消し合いが起きます。三角形 O,pi,pi+1O, p_i, p_{i+1} の重心は pi+pi+13\frac{p_i + p_{i+1}}{3} なので、多角形全体は

S=12∑ipi×pi+1,(Mx,My)=16∑i(pi×pi+1)(pi+pi+1)S = \frac{1}{2} \sum_i p_i \times p_{i+1}, \qquad (M_x, M_y) = \frac{1}{6} \sum_i (p_i \times p_{i+1}) (p_i + p_{i+1})

となります。面積の式は、よく知られた外積で多角形の面積を求める式(靴ひも公式)そのものです。一次モーメントの式はそれを一歩進めたものです。

polygon_edge_moment(p, q) は、辺 p→qp \to q の寄与(三角形 O,p,qO, p, q の符号付き面積と一次モーメント)を返します。分母の 2 と 6 を払った値を持っているので、整数座標なら誤差なく計算できます。

メンバ中身式
area2面積の 2 倍p×qp \times q
mxxx の一次モーメントの 6 倍(p×q)(px+qx)(p \times q)(p_x + q_x)
myyy の一次モーメントの 6 倍(p×q)(py+qy)(p \times q)(p_y + q_y)

全辺の寄与を足すと、多角形全体の PolygonMoment になります。area() は area2 / 2、centroid() は

gx=MxS=mx/6area2/2=mx3⋅area2g_x = \frac{M_x}{S} = \frac{\texttt{mx} / 6}{\texttt{area2} / 2} = \frac{\texttt{mx}}{3 \cdot \texttt{area2}}

を計算しています(gyg_y も同様)。polygon_centroid は、これを全辺について足して重心を返すだけの関数です。

さきほどの L 字形で確かめると、辺ごとの (area2, mx, my) は

辺area2mxmy
(0,0)→(2,0)(0,0) \to (2,0)000
(2,0)→(2,1)(2,0) \to (2,1)282
(2,1)→(1,1)(2,1) \to (1,1)132
(1,1)→(1,2)(1,1) \to (1,2)123
(1,2)→(0,2)(1,2) \to (0,2)228
(0,2)→(0,0)(0,2) \to (0,0)000
合計61515

で、面積 6/2=36/2 = 3、重心 15/(3⋅6)=5/615 / (3 \cdot 6) = 5/6 と、長方形に分けて求めた結果と一致します。

座標が 10910^9 程度だと mx は 102710^{27} 程度になるので、整数座標のときは __int128_t で値を持ちます。

部分多角形の面積と重心を O(1)O(1) で求める

Section titled “部分多角形の面積と重心を O(1)O(1)O(1) で求める”

いちばんの使いみちです。多角形の頂点 u,u+1,…,vu, u+1, \dots, v を順に結んで閉じた部分多角形の面積や重心を、たくさん求めたいとします。

部分多角形の辺は、元の多角形の辺 u→u+1,…,v−1→vu \to u+1, \dots, v-1 \to v と、閉じる辺 v→uv \to u です。モーメントは辺ごとの寄与の和なので、前者は寄与の累積和で O(1)O(1) で求まり、そこに閉じる辺の寄与を 1 つ足せば完成です。PolygonMoment は + と - が使えるので、そのまま累積和に載せられます。頂点の番号が一周をまたぐ場合もあるので、円環上の区間和 CircularSum を使うと便利です。

using P = Vector<long long>;
std::vector<PolygonMoment<long long>> e(n);
for (int i = 0; i < n; i++) e[i] = polygon_edge_moment(ps[i], ps[(i + 1) % n]);
CircularSum cs(e);
// 頂点 u, u+1, ..., v を結んだ部分多角形
auto m = cs.sum(u, v) + polygon_edge_moment(ps[v], ps[u]);
m.area(); // 符号付き面積
m.centroid(); // 重心

辺の寄与は原点の位置によって変わりますが、閉じた多角形について足した合計は原点によりません(打ち消し合いの議論は原点の位置を問わないからです)。途中までの和だけでは意味のある値にならず、閉じる辺を足して初めて部分多角形の値になる、という点に注意してください。

凸多角形を対角線で 2 つに切ったときの面積の差を最小化する、といった問題では、切り方ごとに両側の面積が O(1)O(1) で求まるので、尺取り法や二分探索と組み合わせられます。重心が要る問題でも同じように扱えます。

頂点 pip_i を動かすと、寄与が変わるのは辺 pi−1→pip_{i-1} \to p_i と pi→pi+1p_i \to p_{i+1} の 2 つだけです。PolygonMoment の和は結合的なので、セグメント木に載せれば、頂点の更新と部分多角形のモーメントの取得がそれぞれ O(log⁡n)O(\log n) でできます。

離れた複数の多角形をまとめた図形の重心は、それぞれの PolygonMoment を足してから centroid() を呼べば求まります。穴の開いた図形は、外側から穴を引きます。時計回りの多角形の寄与は符号が反転するので、穴を時計回りで与えれば、外側と穴の寄与をすべて足すだけでも同じ結果になります。

整数座標なら area2, mx, my はすべて整数で、重心は gx=mx/(3⋅area2)g_x = \texttt{mx} / (3 \cdot \texttt{area2}) という分数です。2 つの図形の重心の xx 座標の大小や、重心がある点と一致するかどうかは、分母を払って整数のまま比べられます(分母の符号に注意してください)。centroid() は double を返すので、厳密な判定が必要なときはメンバを直接使います。

ライブラリにはありませんが、同じ考え方で二次モーメントも辺ごとに分解できます。

Ixx=∬Dx2 dA=112∑i(pi×pi+1)(xi2+xixi+1+xi+12)I_{xx} = \iint_D x^2 \, dA = \frac{1}{12} \sum_i (p_i \times p_{i+1}) (x_i^2 + x_i x_{i+1} + x_{i+1}^2)

(xix_i は pip_i の xx 座標。IyyI_{yy} も同様)。L 字形で計算すると Ixx=3I_{xx} = 3 になり、長方形ごとに積分した 83+13\frac{8}{3} + \frac{1}{3} と一致します。

二次モーメントがあると、たとえば図形内の一様ランダムな点と点 cc の距離の 2 乗の期待値が

Ixx+IyyS−2 c⋅g+∣c∣2\frac{I_{xx} + I_{yy}}{S} - 2 \, c \cdot g + |c|^2

で求まります。物理でいう慣性モーメント(回転させにくさ)も、この Ixx+IyyI_{xx} + I_{yy} です。

  • kk 次モーメントは「重さ × 位置の kk 乗」の合計で、図形なら積分。零次は面積、一次は「面積 × 重心」
  • モーメントは図形を分割すると足し算・引き算できるが、重心はそのままでは足せない。だからモーメントで持って、最後に割る
  • 多角形は原点と各辺の三角形に符号付きで分けられるので、モーメントは辺ごとの寄与の和になる
  • 寄与の累積和を取れば、部分多角形の面積と重心が O(1)O(1) で求まる。PolygonMoment はそのための型

ABC481 E - Most Brilliant Starry Sky

xyxy 平面上に NN 個の星 (Xi,Yi)(X_i, Y_i) があります。原点を通り、どの星も通らない直線を 1 本引き、分けられた 2 つの領域のどちらかを選びます。選んだ領域に含まれる星の個数の最大値を求める問題です。

どの 2 個の星も原点と一直線上に並ぶことはありません。TT 個のテストケースに答えます(NN の総和は 2×1052 \times 10^5 以下、∣Xi∣,∣Yi∣≤109|X_i|, |Y_i| \le 10^9)。

原点を通る直線で分けた一方の領域は、偏角(原点から見た向きの角度)が長さ π\pi の開区間 (α,α+π)(\alpha, \alpha + \pi) に入る点の集まりです。よって、偏角が長さ π\pi の区間に入る星の個数の最大値を求めればよいです。

ある領域 (α,α+π)(\alpha, \alpha + \pi) が星を含むとき、含まれる星のうち偏角が最小のものを θ\theta とします。含まれる星の偏角はどれも θ\theta 以上 α+π\alpha + \pi 未満で、α<θ\alpha < \theta なので、どれも [θ,θ+π)[\theta, \theta + \pi) に入ります。逆に、偏角が [θ,θ+π)[\theta, \theta + \pi) に入る星は、α\alpha を θ\theta より少しだけ小さくした領域でちょうど全部含められます。偏角がちょうど θ+π\theta + \pi の星はないので(原点と一直線上に並ばないため)、α\alpha を θ\theta に十分近くすれば余計な星は入りません。

したがって、各星 ii について、偏角が [θi,θi+π)[\theta_i, \theta_i + \pi) に入る星を数え、その最大値が答えです。

星を偏角の順に並べます。偏角は一周すると元に戻るので、偏角に 2π2\pi を足した写しを後ろにつなげた長さ 2N2N の列を作ります。この列で、各 ll (0≤l<N)(0 \le l < N) について、偏角が θl+π\theta_l + \pi 未満である範囲の右端 rr を求めると、r−lr - l が [θl,θl+π)[\theta_l, \theta_l + \pi) に入る星の個数です。ll が増えると rr も減らないので、尺取り法で全体 O(N)O(N) で求まります。

計算量は、偏角ソートの O(Nlog⁡N)O(N \log N) です。

偏角は atan2 などの浮動小数点数で求めると、偏角の近い星の比較で誤差が出るおそれがあります。外積を使って比べると、整数だけで正確に比べられます。座標の絶対値は 10910^9 以下なので、外積は 64 bit 整数に収まります。

C++
#include "shogo-library/base/all"
#include "shogo-library/geometry/angle.hpp"
#include "shogo-library/utility/container_func.hpp"
#include "shogo-library/utility/two-pointers.hpp"
void solve() {
LL(N);
vec<Angle<ll>> A(N);
for (auto &a : A)
std::cin >> a;
sort(A);
rep(i, N) A.push_back(A[i].next_turn());
auto right = two_pointers(2 * N, [&](ll l, ll r) { return A[r] < A[l].opposite(); });
ll ans = 0;
rep(l, N)
chmax(ans, right[l] - l);
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
LL(T);
rep(T)
solve();
}

Angle<ll> はベクトル (x,y)(x, y) の偏角を表す型で、周回数 turn を持ち、偏角 2π⋅turn+[0,2π)2\pi \cdot \mathrm{turn} + [0, 2\pi) として外積で比べます。next_turn() は偏角に 2π2\pi を足したもの、opposite() は π\pi を足したもの(逆向きのベクトル)です。

sort(A) で偏角の順に並べ、next_turn() で 2π2\pi を足した写しを後ろにつなげます。two_pointers(n, can_add) は、各 l について、区間 [l, r) に r を加えてよい(can_add(l, r) が真)間だけ r を伸ばし、伸ばし終えた r を並べた列を返します。ここでは「A[r] の偏角が A[l] の偏角 +π+ \pi 未満」を条件にしています。

使用ライブラリ:cpp_include@4b58304

Codeforces Round 1125 (Div. 3) A - In Search of Convenience

整数 x0,y0,Rx_0, y_0, R が与えられます(−10≤x0,y0≤10-10 \le x_0, y_0 \le 10、1≤R≤251 \le R \le 25)。点 (x0,y0)(x_0, y_0) からの距離がちょうど RR である格子点(座標が整数の点)を 1 つ出力してください。答えが複数あるときは、どれを出力してもかまいません。テストケースは t≤104t \le 10^4 個です。

(x0,y0)(x_0, y_0) から xx 軸の方向にちょうど RR だけずらした点 (x0−R,y0)(x_0 - R, y_0) を出力すればよいです。

RR は整数なので、この点も格子点です。距離は

(x0−(x0−R))2+(y0−y0)2=R2=R\sqrt{(x_0 - (x_0 - R))^2 + (y_0 - y_0)^2} = \sqrt{R^2} = R

となり、ちょうど RR です。

問題文の例のように (5−2)2+(5−1)2=52(5 - 2)^2 + (5 - 1)^2 = 5^2 となる点を探す必要はありません。軸に沿ってずらすだけで条件を満たせます。(x0+R,y0)(x_0 + R, y_0) や (x0,y0±R)(x_0, y_0 \pm R) でもかまいません。

Python
for _ in range(int(input())):
x, y, r = map(int, input().split())
print(x - r, y)

Blitz Round #25 E - Circles are POINTS !

平面上の nn 個の格子点からなる集合があり、そのうち 2 点は base point と呼ばれます。次の 2 種類のクエリを qq 回処理します。

  • 点 (x,y)(x, y) を集合に追加する(まだ集合にない点)
  • 点 (x,y)(x, y) を集合から削除する(集合にあり、base point ではない点)

最初の状態と各クエリの後に、集合のすべての点を通る円が描けるかを判定する問題です。

  • 2≤n≤2⋅1052 \le n \le 2 \cdot 10^5、0≤q≤2⋅1050 \le q \le 2 \cdot 10^5、∣x∣,∣y∣≤106|x|, |y| \le 10^6、テストケースの nn の総和と qq の総和はそれぞれ 2⋅1052 \cdot 10^5 以下

正確な問題文は元の問題ページを見てください。

base point を固定して円で分類する

Section titled “base point を固定して円で分類する”

base point を A,BA, B とします。A,BA, B は削除されないので常に集合にあり、すべての点を通る円があるなら、それは A,BA, B を通る円です。

base point 以外の点 PP について、

  • PP が直線 ABAB 上にあるなら、異なる 3 点が一直線上に並ぶので円は描けません
  • そうでなければ、A,B,PA, B, P を通る円がただ 1 つ決まります

したがって、答えが YES になるのは「直線 ABAB 上の点がなく、base point 以外のすべての点について A,B,PA, B, P を通る円が同じ」ときです。点を「A,B,PA, B, P を通る円」で分類して、種類が 1 種類以下かを見ればよいことになります。

円の中心の座標で分類すると浮動小数点数の誤差が気になるので、整数だけで計算できる量を使います。

AA を原点に平行移動して u=B−Au = B - A とすると、原点と uu を通る円はすべて、あるパラメータ λ\lambda を使って

∣z∣2−z⋅u=λ (u×z)|z|^2 - z \cdot u = \lambda \, (u \times z)

と書けます(⋅\cdot は内積、×\times は外積 x1y2−y1x2x_1 y_2 - y_1 x_2)。

この形に書ける理由

平面上の円は、ww を定数ベクトル、FF を定数として

∣z∣2+w⋅z+F=0|z|^2 + w \cdot z + F = 0

と書けます(中心 −w/2-w/2、半径の 2 乗 ∣w∣2/4−F|w|^2/4 - F)。

  • 原点を通るので、z=0z = 0 を代入して F=0F = 0
  • uu を通るので、z=uz = u を代入して ∣u∣2+w⋅u=0|u|^2 + w \cdot u = 0

後者について、w=−u+dw = -u + d とおくと

∣u∣2+(−u+d)⋅u=d⋅u=0|u|^2 + (-u + d) \cdot u = d \cdot u = 0

となるので、dd は uu に直交するベクトルです。uu を 90° 回したベクトルを u⊥=(−uy,ux)u^\perp = (-u_y, u_x) とすると、uu に直交するベクトルは u⊥u^\perp の実数倍なので、d=−λ u⊥d = -\lambda\, u^\perp (λ∈R\lambda \in \mathbb{R}) と書けます。よって

w=−u−λ u⊥w = -u - \lambda\, u^\perp

です。これを代入し、u⊥⋅z=uxzy−uyzx=u×zu^\perp \cdot z = u_x z_y - u_y z_x = u \times z を使うと

∣z∣2−z⋅u=λ (u×z)|z|^2 - z \cdot u = \lambda\, (u \times z)

になります。

どの λ\lambda でも w≠0w \ne 0 なので半径の 2 乗 ∣w∣2/4|w|^2/4 は正で、本物の円になります。また、円が決まれば係数 ww が決まり、ww から λ\lambda が決まります。つまり、A,BA, B を通る円と実数 λ\lambda は 1 対 1 に対応します。

z=P−Az = P - A を代入して λ\lambda について解くと

λ=(P−A)⋅(P−B)(B−A)×(P−A)\lambda = \frac{(P - A) \cdot (P - B)}{(B - A) \times (P - A)}

です。円と λ\lambda は 1 対 1 に対応するので、2 点について A,BA, B とそれぞれを通る円が同じであることと、それぞれから求めた λ\lambda が等しいことは同値です。分母が 00 になるのは PP が直線 ABAB 上にあるときです。

λ\lambda は分子・分母とも整数なので、gcd で約分して分母を正にそろえた (分子, 分母) の組を辞書のキーにすれば、誤差なく分類できます。

base point 以外の点のキーの個数を Counter で持ち、追加・削除のたびに増減します。直線 ABAB 上の点はキーを None にしておけば、

  • None がない
  • キーの種類が 1 種類以下

のとき YES です。各点のキーの計算は gcd 1 回なので、座標の範囲を CC として全体で O((n+q)log⁡C)O((n + q) \log C) です。

公式解説も、base point A,BA, B を固定して各点 PP について A,B,PA, B, P を通る円を考える点は同じです。直線 ABAB 上にある点の個数と、A,B,PA, B, P の外接円の中心(外心)の集合を管理し、直線上の点がなく外心がすべて一致するときに YES としています。外心は 2 本の垂直二等分線の交点として計算しています。

Python(upsolve)
from math import gcd
from collections import Counter
for _ in range(int(input())):
n, q, a, b = map(int, input().split())
P = [tuple(map(int, input().split())) for _ in range(n)]
ax, ay = P[a - 1]
bx, by = P[b - 1]
ux, uy = bx - ax, by - ay
def key(x, y):
# λ = (P-A)・(P-B) / (B-A)×(P-A) を約分したもの。直線 AB 上なら None
num = (x - ax) * (x - bx) + (y - ay) * (y - by)
den = ux * (y - ay) - uy * (x - ax)
if den == 0:
return None
if den < 0:
num, den = -num, -den
g = gcd(num, den)
return (num // g, den // g)
cnt = Counter()
for i, (x, y) in enumerate(P):
if i != a - 1 and i != b - 1:
cnt[key(x, y)] += 1
def ok():
return None not in cnt and len(cnt) <= 1
print("YES" if ok() else "NO")
for _ in range(q):
c, x, y = input().split()
x, y = int(x), int(y)
k = key(x, y)
if c == "+":
cnt[k] += 1
else:
cnt[k] -= 1
if cnt[k] == 0:
cnt.pop(k)
print("YES" if ok() else "NO")