Day 151-Q5 | Radonの定理（Radon Partition）

問題

平面上の4点$p_1,p_2,p_3,p_4$（整数座標、どの3点も一直線上にない）が与えられる。以下の構成的証明の手続きに従って、Radon分割とその交点を求めよ。

手続き

$\sum\lambda_ix_i=0,\ \sum\lambda_iy_i=0,\ \sum\lambda_i=0$（3本の式・4個の未知数、解は定数倍を除いて一意）を解く。
整数化し$\gcd=1$に正規化。最初の非ゼロ$\lambda_i$が正になるよう符号を揃える。
$\lambda_i>0$の添字集合を$I^+$、$\lambda_i<0$を$I^-$とする。
交点 $q=\dfrac{\sum_{i\in I^+}\lambda_ip_i}{\sum_{i\in I^+}\lambda_i}$ を計算する（$I^-$側の式でも同じ点になる）。

$\lambda_1,\dots,\lambda_4$、$I^+$、$I^-$、交点$q$を既約分数で出力せよ。

入力形式

x1 y1
x2 y2
x3 y3
x4 y4

制約

$-1000 \le x_i,y_i \le 1000$

どの3点も一直線上にない

入出力例

入力例1

出力例1

入力例2

出力例2

13 -11 -21 19
2 1 4
2 2 3
19/8 95/32

概念図：正方形の対角線が交わる点がRadon分割の交点

ヒント（段階的開示）

ヒント1（方向性）

「4点を2組に分けて凸包を交わらせる」という主張は図を描けば直感的に納得できる。この問題ではそれを「解を持つ連立方程式を解く」という機械的な手順で構成する。

ヒント2（アプローチ）

未知数4個・方程式3本なので、$\lambda_4=1$と固定し残り3つを$3\times3$の連立一次方程式として解く。座標が整数でも解は分数になりうるので、厳密有理数演算(fractions.Fraction)を使う。

ヒント3（誘導）

from fractions import Fraction as F
# x1 l1 + x2 l2 + x3 l3 = -x4   (l4=1 とおく)
# y1 l1 + y2 l2 + y3 l3 = -y4
#    l1 +    l2 +    l3 = -1
# の3x3連立方程式をクラメルの公式で解き、l1,l2,l3,l4=1 を得る
# → 分母のLCMを掛けて整数化 → gcdで割って既約化 → 符号を正規化

模範解答 (Python)

import sys
from fractions import Fraction as F
from math import gcd
from functools import reduce

def main():
    data = sys.stdin.read().split()
    pts = []
    for i in range(4):
        x = int(data[2 * i]); y = int(data[2 * i + 1])
        pts.append((x, y))

    xs = [F(p[0]) for p in pts]
    ys = [F(p[1]) for p in pts]
    A = [
        [xs[0], xs[1], xs[2]],
        [ys[0], ys[1], ys[2]],
        [F(1), F(1), F(1)],
    ]
    b = [-xs[3], -ys[3], F(-1)]

    def det3(m):
        return (m[0][0] * (m[1][1] * m[2][2] - m[1][2] * m[2][1])
                - m[0][1] * (m[1][0] * m[2][2] - m[1][2] * m[2][0])
                + m[0][2] * (m[1][0] * m[2][1] - m[1][1] * m[2][0]))

    D = det3(A)
    sols = []
    for col in range(3):
        Ai = [row[:] for row in A]
        for r in range(3):
            Ai[r][col] = b[r]
        sols.append(det3(Ai) / D)
    lam = sols + [F(1)]

    denoms = [x.denominator for x in lam]
    def lcm(a, b_): return a * b_ // gcd(a, b_)
    L = reduce(lcm, denoms, 1)
    ints = [int(x * L) for x in lam]
    g = reduce(gcd, [abs(v) for v in ints])
    ints = [v // g for v in ints]
    for v in ints:
        if v != 0:
            if v < 0:
                ints = [-w for w in ints]
            break

    pos = [i + 1 for i, v in enumerate(ints) if v > 0]
    neg = [i + 1 for i, v in enumerate(ints) if v < 0]

    sp = sum(ints[i - 1] for i in pos)
    ix = sum(ints[i - 1] * pts[i - 1][0] for i in pos)
    iy = sum(ints[i - 1] * pts[i - 1][1] for i in pos)
    fx = F(ix, sp)
    fy = F(iy, sp)

    print(" ".join(map(str, ints)))
    print(len(pos), " ".join(map(str, pos)))
    print(len(neg), " ".join(map(str, neg)))
    print(f"{fx.numerator}/{fx.denominator} {fy.numerator}/{fy.denominator}")

main()

Step-by-Step 解説

1例1で連立方程式を解く
$\lambda_4=1$とおき$x$式$2\lambda_2=-2$、$y$式$2\lambda_2+2\lambda_3=0$、和の式$\lambda_1+\lambda_2+\lambda_3=-1$から$(\lambda_1,\lambda_2,\lambda_3,\lambda_4)=(-1,-1,1,1)$。

2正規化
整数・$\gcd{=}1$は既に満たすが、最初の非ゼロ$\lambda_1{=}{-1}$が負なので全体反転して$(1,1,-1,-1)$。

3分割と交点
$I^+{=}\{1,2\}$（$p_1,p_2$）、$I^-{=}\{3,4\}$（$p_3,p_4$）。$q=\dfrac{1\cdot(0,0)+1\cdot(2,2)}{2}=(1,1)$。これは正方形の対角線$p_1p_2$と$p_3p_4$の交点（中心）と一致する。

4例2で分数になる場合
同じ手順で$(\lambda_1,\dots,\lambda_4)=(13,-11,-21,19)$、$I^+{=}\{1,4\}$、$I^-{=}\{2,3\}$、交点$(19/8,95/32)$。$I^-$側の式でも$\dfrac{11(5,1)+21(1,4)}{32}=(19/8,95/32)$と完全一致し、交点が両方の凸包に同時に属することを裏付ける。

よくあるミス

ミス	原因	正しい書き方
浮動小数点で解いてgcd判定が誤動作	`float`をそのまま使う	`fractions.Fraction`で厳密演算し、最後に整数化してgcdを取る
符号の正規化を忘れる	符号の自由度を放置	「最初の非ゼロ成分を正にする」ルールで出力を一意化
$I^-$側の交点計算で分母の符号を間違える	$\lambda_i$が負であることを忘れる	$I^+$は$\sum\lambda_i$（正）、$I^-$検算は$-\sum\lambda_i$（正）で割る
3点が一直線上の退化ケースを想定しない	一般の位置を過信	本問は制約で保証されるが、実務では行列式0のケースの別処理が必要
既約分数化で符号の置き場が一貫しない	`Fraction`の内部表現に頼りきる	Pythonの`Fraction`は分母を常に正に保つ仕様なのでそのまま出力すればよい

次のステップ

発展: Radonの定理は一般の$d$次元・$d+2$点に一般化される。3次元・5点の場合を試してみる。
次回予告: 次回のテーマは学習の進行に応じて選定

自己評価

完全理解おおむね理解要復習

Day 151-Q5 — Radonの定理の構成的証明（Radon Partition）

問題

手続き