• home
  • about
  • 全ての投稿
  • ソフトウェア・ハードウェアの設定のまとめ
  • 分析関連のまとめ
  • ヘルスケア関連のまとめ
  • 生涯学習関連のまとめ

rounding error

date: 2020-05-16 excerpt:

tag: rounding error競プロ


rounding error

気づかないとなんで WA したかわからない

例

https://yukicoder.me/problems/no/1041 にて、解析的に解けるだろうと期待したが、以下のコメントの箇所にてエラーを起こしていた。

n=int(input())

ps = []
for _ in range(n):
    a,b=map(int,input().split())
    ps.append((a,b))

from itertools import combinations

pset = set()

special_x = set()
special_y = set()
for p1, p2 in combinations(ps,2):
    if p2[0] != p1[0]:
        katamuki = (p2[1] - p1[1])/(p2[0] - p1[0])
        takasa = p1[1] - katamuki*p1[0]
        pset.add((katamuki, takasa))
    if p2[0] == p1[0]:
        special_x.add(p1[0])
    if p2[1] == p1[1]:
        special_y.add(p1[0])
        
cs = []
for katamuki, takasa in pset:
    c = 0
    for p in ps:
        if abs(p[1] - (p[0]*katamuki + takasa)) < 0.0001: # ココ
            c += 1
    cs.append(c)
for special in special_x:
    c = 0
    for p in ps:
        if p[0] == special:
            c += 1
    cs.append(c)
for special in special_y:
    c = 0
    for p in ps:
        if p[1] == special:
            c += 1
    cs.append(c)

p[1] == p[0]*kamuki + takasa としていたため、floatは厳密解でなくなるという特徴を持つのでエラーが発生することになった。

対処法

  • floatを含む計算ではこのリスクを意識すること
  • 整数でどうにか表現して整数として特など


rounding error競プロ Share Tweet