座標を入力し平行判定をするという問題です。
以下のソースだと通らないのですが、何が原因なのでしょうか?
返されるのはWrong Answerです
n = gets.to_i date = [] n.times do x1,y1,x2,y2,x3,y3,x4,y4 = gets.chomp.split.map(&:to_f) if (y2 - y1)/(x2 - x1) == (y4 - y3)/(x4 - x3) date << "YES" else date << "NO" end end n.times do |ni| puts date[ni] end #$ #2 #0.0 0.0 1.0 1.0 1.0 0.0 2.0 1.0 #3.0 2.0 9.0 6.0 13.0 5.0 7.0 9.0 #YES #NO
気になる質問をクリップする
クリップした質問は、後からいつでもMYページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2018/10/07 00:26
回答3件
0
ベストアンサー
2点あります。
一つ目は浮動小数点数は正確に表現できないと言うことです。"0.1"をFloatにした場合、その値は正確に0.1(分数で言えば1/10)という数値ではありません。そのため、どこかで誤差が出てきます。==
での比較はその小さな誤差すらも異なるモノと判断してしまうため、Wrong Answerになります。
これを解消するには三つの方法があります。
- 有理数として計算する。(RubyではRatinoalを使う。言語によっては標準で存在せず、競プロでは使えない場合がある)
- 任意精度の10進数浮動小数点数として計算する。(RubyではBigDecimalを使う)
- 精度分の桁を掛けた値である整数にして計算する。(整数同士の演算は整数になることに注意)
Rubyならto_r
でRationalにした方が簡単でしょう。他言語であれば、BigDecimal相当のライブラリを使う必要が出てきます。
二つ目はkaztoさんが指摘したとおり、x1
とx2
が同じの場合、および、x3
とx4
が同じの場合、ゼロ除算が行われると言うことです。RubyではFloatへの0除算はInfinitiyまたは-Infinitiyを返すのでエラーになりません(BigDecimalも同じ)。しかし、IntegerやRationalの場合は例外になりますので、注意が必要です。BigDecimalで計算する場合も、正と負のどちらのInfinityであっても傾きは一緒であると言うことも注意すべき事でしょう。
投稿2018/10/07 01:07
編集2018/10/07 01:11総合スコア21733
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
v.rb
ruby
1DELTA = 1.0e-10 2 3def judge(x1, y1, x2, y2, x3, y3, x4, y4) 4 if ((x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3)).abs < DELTA 5 "YES" 6 else 7 "NO" 8 end 9end 10 11puts(judge(0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 2.0, 1.0)) 12puts(judge(3.0, 2.0, 9.0, 6.0, 13.0, 5.0, 7.0, 9.0)) 13puts(judge(3.0, 2.0, 9.0, 6.0, 13.0, 5.0, 7.0, 1.0)) 14 15TESTS = [ 16 [ 0, 0, 0,-1, 0, 0, 0,-1, 'YES'], 17 [ 0, 0, 0,-1, 0, 0, 0, 0, 'YES'], 18 [ 0, 0, 0,-1, 0, 0, 0, 1, 'YES'], 19 [ 0, 0, 0,-1, 0, 0,-1,-1, 'NO'], 20 [ 0, 0, 0,-1, 0, 0,-1, 0, 'NO'], 21 [ 0, 0, 0,-1, 0, 0,-1, 1, 'NO'], 22 [ 0, 0, 0,-1, 0, 0, 1,-1, 'NO'], 23 [ 0, 0, 0,-1, 0, 0, 1, 0, 'NO'], 24 [ 0, 0, 0,-1, 0, 0, 1, 1, 'NO'], 25 26 [ 0, 0, 1, 0, 0, 0, 0,-1, 'NO'], 27 [ 0, 0, 1, 0, 0, 0, 0, 0, 'YES'], 28 [ 0, 0, 1, 0, 0, 0, 0, 1, 'NO'], 29 [ 0, 0, 1, 0, 0, 0,-1,-1, 'NO'], 30 [ 0, 0, 1, 0, 0, 0,-1, 0, 'YES'], 31 [ 0, 0, 1, 0, 0, 0,-1, 1, 'NO'], 32 [ 0, 0, 1, 0, 0, 0, 1,-1, 'NO'], 33 [ 0, 0, 1, 0, 0, 0, 1, 0, 'YES'], 34 [ 0, 0, 1, 0, 0, 0, 1, 1, 'NO'], 35 36 [ 0, 0, 1, 1, 0, 0, 0,-1, 'NO'], 37 [ 0, 0, 1, 1, 0, 0, 0, 0, 'YES'], 38 [ 0, 0, 1, 1, 0, 0, 0, 1, 'NO'], 39 [ 0, 0, 1, 1, 0, 0,-1,-1, 'YES'], 40 [ 0, 0, 1, 1, 0, 0,-1, 0, 'NO'], 41 [ 0, 0, 1, 1, 0, 0,-1, 1, 'NO'], 42 [ 0, 0, 1, 1, 0, 0, 1,-1, 'NO'], 43 [ 0, 0, 1, 1, 0, 0, 1, 0, 'NO'], 44 [ 0, 0, 1, 1, 0, 0, 1, 1, 'YES'], 45 46 [ 0, 0, 0, 1, 0, 0, 0,-1, 'YES'], 47 [ 0, 0, 0, 1, 0, 0, 0, 0, 'YES'], 48 [ 0, 0, 0, 1, 0, 0, 0, 1, 'YES'], 49 [ 0, 0, 0, 1, 0, 0,-1,-1, 'NO'], 50 [ 0, 0, 0, 1, 0, 0,-1, 0, 'NO'], 51 [ 0, 0, 0, 1, 0, 0,-1, 1, 'NO'], 52 [ 0, 0, 0, 1, 0, 0, 1,-1, 'NO'], 53 [ 0, 0, 0, 1, 0, 0, 1, 0, 'NO'], 54 [ 0, 0, 0, 1, 0, 0, 1, 1, 'NO'], 55 56] 57TESTS.each do |test| 58 p("ERROR #{test}") if test[-1] != judge(*test[0..-2]) 59end
ベクトルの外戚を計算して、平行かを判定しています。
割り算はあらられません。
あたえらた座標から直線にならない (点になる) 場合は、平行と判定することにしています。
stdinからの入力でなく、プログラム中にデータと判定結果を書いておき、判定メソッドのテストをしています。
参考情報
- 2直線の直交判定・平行判定
http://www.deqnotes.net/acmicpc/2d_geometry/products
...
// 外積 (cross product) : a×b = |a||b|sinθ
double cross(P a, P b) {
return (a.real() * b.imag() - a.imag() * b.real());
}
...
// 2直線の平行判定 : a//b <=> cross(a, b) = 0
int is_parallel(P a1, P a2, P b1, P b2) {
return EQ( cross(a1-a2, b1-b2), 0.0 );
}
...
投稿2018/10/07 12:09
総合スコア22324
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
あなたの回答
tips
太字
斜体
打ち消し線
見出し
引用テキストの挿入
コードの挿入
リンクの挿入
リストの挿入
番号リストの挿入
表の挿入
水平線の挿入
プレビュー
質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。