Atcoder Biginner Contest 224 C問題が不正解及びTLEとなる

Question

Atcoder Biginner Contest 224 C問題についての質問です。問題は以下です。
https://atcoder.jp/contests/abc224/tasks/abc224_c
私の回答方針は3点の全ての組み合わせを求め、それぞれの辺の長さを求めます。そして三角形の成立条件であるA+B>CかつA+C>BかつB+C>Aとなればcountを+1するというものです。下のコードを提出すると不正解及びTLE(実行時間超過)となってしまいます。
解説(https://atcoder.jp/contests/abc224/editorial/2810)を見ると全ての組み合わせを実行することは問題ないそうです(この辺はまだわかっていません)。おそらくTLEとなってしまうことはnormの計算やif文での演算部によって超過してしまうのではないかと考えています。
また、方針自体は異なっていても成立条件は誤っていないはずなのでTLEとなることはあったとしても不正解となることの原因がわかりません。私自身の見解ですが、有効数字によって辺の少しの差の条件が通っていないのではないかと考えています。
以上の2つの点(なぜTLE、WAとなるのか)に関して、何か考えられる原因がありましたら教えていただきたいです。
・提出コード

import itertools
import numpy as np

N = int(input())
coor = []
for _ in range(N):
    coor.append(list(map(int,input().split())))

count = 0
for v in itertools.combinations(range(N),3):
    a = np.array(coor[v[0]])
    b = np.array(coor[v[1]])
    c = np.array(coor[v[2]])
    #print(a,b,c)
    ab = np.linalg.norm(a-b)
    ac = np.linalg.norm(a-c)
    bc = np.linalg.norm(b-c)
    #print(ab,bc,ac)
    if ab+ac>bc and ab+bc>ac and ac+bc>ab:
        count += 1
print(count)

Answer 1

有効数字の問題だと思うのなら、極端な数字で試せばわかるでしょう。(正しい出力は1)

3
1000000000 1000000000
-1000000000 -1000000000
0 1

TLEのほうは、おそらく距離の計算でしょう。
平方根の計算には、それなりに時間がかかりそうです。

---

もう少し分かりやすい三角形をベースに、ざっくりとした説明を試みます。

座標(x,0)(-x,0)(0,1)からなる二等辺三角形を考えます(x>0)。
そうすると、底辺の長さが2x、斜辺の長さが√(x^2+1)となります。

ここで、xは10^9以下なので、x^2は最大20桁になりますが、floatの有効桁は16桁弱なので、表現しきれません。
そうなると、x^2に+1したとしても変化が少なすぎて表現しきれず、x^2のままとなります。
よって、xが大きい場合、この三角形の斜辺はxとなり、三角形の条件を満たさなくなります。

実際には、x=67108864にて斜辺の長さがxと等しくなります。
x^2はfloatの有効桁の限界まで到達していませんが、sqrt後の値とxとの差が限界を超えたのでしょう。
実際、直前の67108863での計算結果は、16桁の数値となっています。

>>> import math
>>> math.sqrt(67108863*67108863+1)
67108863.00000001
>>> math.sqrt(67108864*67108864+1)
67108864.0

Answer 2

以下の入力データの場合、出力は0になるはずですが、tana1021さんのコードでは1が出力されます。
そのため、不正解となります。

3
1 0
2 0
3 0

上記は間違っていました。

原因は、整数と浮動小数点数の問題です。
np.linalg.normは浮動小数点数を返すので、actorbugさんが書かれているように誤差が出てしまいます。
途中で浮動小数点数を使うと誤差は回避できません。
言い換えれば、全てを整数演算で行えば正しく計算できるでしょう。

ヒントは「平行」です。

Comments

[tana1021]

その入力ですとab=1,ac=2,bc=1となるため出力は0となります。実際にプログラムを動かしても0となりました。