sidchelseafan's blog

SPOJ _ — Game Of Lines.
By sidchelseafan, 10 years ago, In English

Your text to link here... Hi, I was doing this problem on SPOJ. It basically asks us to find total number of distinct slopes among n different points. Pretty easy( n <= 200).

So I did it using two approaches. First, I run two loops calculating all the slopes (the points are integers,and I took care and took input as doubles) and insert them in a set < double > taking care of case when dx =0 (slope = dy/dx). This approach got WA.

In second, I do the same thing but I push the slopes in a vector and then sort the vector and take care of duplicates. This Got AC.

Your text to link here...- Approach 1.-WA

Your text to link here...- Approach 2.- AC.

Can someone explain me the reason for this.

Thank You.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +10 Vote: I do not like it

One does not simply check equality in doubles by ==, !=. Identical doubles can differ in the last few significant digits, so you should check if their absolute difference is small enough.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Oh !. But regardless, it worked in the second approach. I don't know why using a set gave WA and vector AC. Could you be more explicit. Thank You.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My guess is luck or that equality comparison with doubles messes up sets somehow.

      → Reply