DMOPC '19 Contest 6 P1 - Grade 9 Math

View as PDF
Submit solution
Points: 7
Time limit: 2.0s
Memory limit: 256M
Author:
little_prince
Problem types

Veshy is struggling in math class so he asks you for help (again). You are given two lines each defined by a pair of distinct points, (x_1,y_1) and (x_2,y_2), x_1,y_1,x_2,y_2 \in \mathbb Z. You are to find if the two lines are parallel, coincident, or intersecting.

Input Specification

The input will consist of two lines.
The first line of input will consist of four space-separated integers in the following order: x_1, y_1, x_2, y_2, the coordinates of the two points that define the first line.
The second line of input is the same format as the first line containing the coordinates of the points defining the second line.
In all cases, -250 \le x_1, y_1, x_2, y_2 \le 250.

Output Specification

If the lines are coincident, output coincident.
If the lines are parallel but not coincident, output parallel.
If the lines intersect, output the point of intersection (x, y) in the form x y.
Output your answer to 6 decimal places. Your answer will be considered correct if its absolute or relative error does not exceed 10^{-6}.

Sample Input 1

0 0 1 1
-1 -1 -2 -2

Sample Output 1

coincident

Sample Input 2

0 0 1 2
2 0 3 2

Sample Output 2

parallel

Sample Input 3

0 0 0 4
-2 6 2 6

Sample Output 3

0.000000 6.000000

Comments


  • -9
    DsaidyB  commented on Aug. 6, 2020, 8:24 p.m. ← edit 6

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 2
      boolean  commented on Aug. 6, 2020, 9:20 p.m. ← edited

      You should refer to the DMOJ discord for help with your code. Also, I'm also not completely sure if you handled the undefined slope case properly.


      • 2
        DsaidyB  commented on Aug. 8, 2020, 7:22 p.m.

        Okay


  • 1
    ross_cleary  commented on March 30, 2020, 4:40 p.m.

    Is it possible to AC with a solution that finds the slope and y-intercept and handles exception cases separately?


    • 2
      richardzhang  commented on March 30, 2020, 5:18 p.m.

      You can't find slope without handling exception cases. What if you get the slope \frac{something}{0}?


      • 1
        ross_cleary  commented on March 30, 2020, 8:12 p.m.

        Pretty much I am wondering if there is a correct solution that solves the problem using y = mx + b form when neither line has an undefined slope (the two x-values are the same), and handles the case where either one or both of the lines have an undefined slope separately. Because this is the way I did it and I am wrong answering on case #52.


        • 2
          lilweege  commented on March 30, 2020, 9:11 p.m. ← edited

          I was also getting WA on case #52 and using slope-intercept form, even after trying to handle all edge cases.


          • 1
            Auferetur  commented on March 30, 2020, 10:31 p.m.

            Floating point division is bad. Try to avoid it as much as possible in your code.


            • 0
              ross_cleary  commented on March 31, 2020, 2:21 a.m.

              Can you avoid this by merging the final calculation into one big equation and not storing values for intermediate steps.


              • 7
                Xenosi  commented on March 31, 2020, 4:17 p.m. ← edited

                There is a solution that solves this problem using slope y-intercept form, although it is more annoying to code than standard form. If you having trouble with case 52, I recommend that wherever you compare two doubles (using == or !=), to use epsilons to check if they are the same instead. Floating point division is accurate enough for the small range of -250 to 250.


                • -1
                  Winbigwok  commented on April 1, 2020, 6:08 a.m.

                  Test case #52 is a rounding error question. Adding margin for error works too.


                  • 0
                    ross_cleary  commented on April 1, 2020, 9:00 p.m.

                    What do you mean by adding margin for error?


                    • 4
                      RyanLi  commented on April 1, 2020, 11:01 p.m. ← edited

                      Instead of comparing floats directly, you can do something like

                      if (abs(float1 - float2) < 0.0001)

                      So 7.00000001 would be considered equal to 7.0


                      • 0
                        ross_cleary  commented on April 1, 2020, 11:29 p.m.

                        That works, thank you!


  • -1
    harry7557558  commented on March 30, 2020, 3:18 p.m. ← edited

    Note: Make sure -0.000000 is not in your output.

    Edit: I made a mistake.


    • 6
      Tzak  commented on March 30, 2020, 6:05 p.m.

      It shouldn't matter, my submission produces -0.000000 and still passes.