#Advent Calendar Contest 2023 - A Intriguing Triangle ''' ■余弦定理ごり押し版 AB,AC,AD,AE = b,c,d,e BD,DE,EC = x,a,y BD+DE+EC = z ∠ABC,∠ACB = B,C ∠BAD,∠CAE = θ1,θ2 と定義し、x,y(,z)の全探索を行う。 三角形の成立条件より、探索範囲を以下の通りに絞る。 b + c > z, c + z > b, z + b > c ・・・(1) △ABCの余弦定理より c^2 = b^2 + z^2 - 2bz cosB b^2 = c^2 + z^2 - 2cz cosC ・・・(2) ∠ABC(=B),∠ACB(=C)に着目した△ABD,△ACEの余弦定理より d^2 = b^2 + x^2 - 2bx cosB e^2 = c^2 + y^2 - 2cy cosC ・・・(3) (2)のcosB,cosCを(3)に代入し、両辺をz倍すると zd^2 = zb^2 + zx^2 - x(b^2 + z^2 - c^2) ze^2 = zc^2 + zy^2 - y(c^2 + z^2 - b^2) ・・・(4) となる。(4)の右辺は整数型である。 ∠BAD(=θ1),∠CAE(=θ2)に注目した△ABD,△ACEの余弦定理より x^2 = b^2 + d^2 - 2bd cosθ1 y^2 = c^2 + e^2 - 2ce cosθ2 ・・・(5) 0° < θ1,θ2 < 180°のとき、θ1 = θ2 と cosθ1 = cosθ2 は等価である。 さらに cosθ1 = cosθ2 に対して(5)を代入・整理すると、条件は ce(b^2 + d^2 - x^2) = bd(c^2 + e^2 - y^2) ・・・(6) となる。 この式を愚直に評価したいのだが、d,eは整数型と限らないため誤差が生じる。 (誤差評価は行っていませんが、誤差を10^(-6)まで許容するとACするようです) なので誤差が生じない、整数型での評価を目指す。 (6)の両辺を2乗後にz^3倍すると c^2 * ze^2 * (zb^2 + zd^2 - zx^2)^2 = b^2 * zd^2 * (zc^2 + ze^2 - zy^2)^2 ・・・(7) となる。ここでb,c,x,y,zは整数であり、(4)よりzd^2,ze^2も整数である。 従って(7)は整数型で評価可能である。 (7)の変形、もしかしたら b^2 + d^2 - x^2 > 0, c^2 + e^2 - y^2 > 0 の証明が必須? △ABCが成立するとき、△ABD, △ACEも成立するので、三角形の成立条件より b + d > x, c + e > y が成り立つ。両辺を2乗し、x^2やy^2を移項すると証明できる。 が、これは必要かは自信ありません ■誤差どうなるの(要検証) 直感的には、decimal.Decimalを使えば大丈夫。有効数字28桁。 float型(小数点以下16桁)だとちょっとまずそう。 (2)のcosB,cosCを(3)に代入した「だけ」だと d^2 = b^2 + x^2 - (b^2 + z^2 - c^2)x/z e^2 = c^2 + y^2 - (c^2 + z^2 - b^2)y/z ・・・(8) となる。/zの部分で浮動小数点誤差が生じ、(8)で求めるd^2,e^2の誤差は高々10^-16。 √(10^-16) = 10^-8 なので、√を取ると誤差がでかくなる(適当) のでd,eの誤差は高々10^-8としておく。 評価したい式は ce(b^2 + d^2 - x^2) = bd(c^2 + e^2 - y^2) ・・・(6) で、対称性から左辺と右辺の誤差評価結果は等しい。 とりあえず左辺を考えると、c(≒10^2) * e(最大誤差10^-8) * (d^2+e^2-x-2 (≒10^4)) なので誤差が10^-2までありえる、本当かこれ?実験するか。 ce(b^2 + d^2 - x^2) - bd(c^2 + e^2 - y^2) ・・・(9) として、(9)の誤差を雑に探索。 本来正解(誤差 == 0)になるはずの場合、(9)は±2.9 * 10^-8 程度ぶれる。 (a,b,c,x,y,z) = (44,66,96,11,20,75), (40,98,70,9,5,54), (9,100,80,41,32,82) など 逆に本来不正解(誤差 != 0)の場合、(9)は± 4.2 * 10^-2 程度にまで迫る。 (a,b,c,x,y,z) = (67,69,25,7,1,75), (76,57,55,17,16,109), (34,22,63,1,7,42) など 10^-2に迫るのが怖いが、ともあれ本制約下では、 abs( (9) ) < 10^-2 ~ 10^-7 ならYes で評価すれば犯罪ACできる・・・と思う。 ''' #入力受取 a,b,c = [int(input()) for _ in range(3)] #BD,DE,EC = x,a,y BD+DE+EC = z として、x,y,zの全探索を行う for z in range(a, b+c): #三角形の成立条件を確認 if b+c <= z or c+z <= b or z+b <= c: continue #x,yの全探索 for x in range(1,z): y = z-(x+a) if y<1: continue #zd^2,ze^2 = D,E として(4)を計算 D = z * b**2 + z * x**2 - x * (b**2 + z**2 - c**2) E = z * c**2 + z * y**2 - y * (c**2 + z**2 - b**2) #(7)が成立するか確認 if c**2 * E * (z * b**2 + D - z * x**2)**2 == \ b**2 * D * (z * c**2 + E - z * y**2)**2: print('Yes'); exit() #条件を満たす三角形がなければNoを出力 print('No') #ここからデバッグ用 import math from time import perf_counter as pf from random import randint as ri def check_clear(b,c,x,y,z): #整数値で評価 D = z * b**2 + z * x**2 - x * (b**2 + z**2 - c**2) E = z * c**2 + z * y**2 - y * (c**2 + z**2 - b**2) return (c**2 * E * (z * b**2 + D - z * x**2)**2)-\ (b**2 * D * (z * c**2 + E - z * y**2)**2) def check_about(b,c,x,y,z): #小数点誤差を許容 D = b**2 + x**2 - (b**2 + z**2 - c**2)*x/z E = c**2 + y**2 - (c**2 + z**2 - b**2)*y/z return c*math.sqrt(E)*(b**2 + D - x**2) - b * math.sqrt(D) * (c**2 + E - y**2) def check_all(): ans = [] S = pf() corner = 10**18 cb,cc,cx,cy,cz = 0,0,0,0,0 for b in range(1,101): if b%10==0: print('progress:',b) print('section time:',pf()-S) S=pf() for c in range(1,101): for x in range(1,101): for y in range(1,101): for a in range(1,101): z = x+y+a if b+c<=z or c+z<=b or z+b<=c: continue if check_clear(b,c,x,y,z) == 0: ans.append((check_about(b,c,x,y,z),b,c,x,y,z)) else: p = check_about(b,c,x,y,z) if abs(p) < abs(corner): corner = p cb,cc,cx,cy,cz = b,c,x,y,z return ans,corner,cb,cc,cx,cy,cz def check_rand(time): S=pf() corner = 10**18 ca,cb,cc,cx,cy,cz = 0,0,0,0,0,0 while pf()-S < time: b,c,x,y,a = [ri(1,100) for _ in range(5)] z = x+y+a if b+c<=z or c+z<=b or z+b<=c: continue if check_clear(b,c,x,y,z) != 0: p = check_about(b,c,x,y,z) if abs(p) < abs(corner): corner = p ca,cb,cc,cx,cy,cz = a,b,c,x,y,z return corner,ca,cb,cc,cx,cy,cz