Problem 77 Point to Segment Distance
Back to General discussions forum
This problem is really frustrating me... Rodion, would you mind looking at my code and giving me some tips as to why my answer is incorrect? It seems that most all of the values are correct, but not all...
Thanks,
Christopher P. Matthews
Hello, Christopher! Glad to hear from you!
> would you mind looking at my code and giving me some tips as to why my answer is incorrect?
BTW, wouldn't you mind giving an example of input / output data for cases which are incorrect? Probably this will help us to find out the trouble easier :)
For example, here is my answer:
10.173873023961539 15.641751294584754 15.0 8.180789155290551 17.840189840381633 8.026314549007946
9.978360866871855 3.1622776601683795 5.366563145999495 5.366563145999495 6.063390625908324
1.4214846311870668 17.0 13.944852939803557 9.391485505499116 10.0 3.1529631254723287 0.0
11.926054218842427 13.184386762327724 2.604729426373378 6.401843996644799 6.872141438050642
And here is expected answer:
10.173873024 15.6524758425 15 9.21954445729 17.8401898404 8.02631454901 9.97836086687 3.16227766017
5.366563146 5.366563146 7.07106781187 2.2360679775 17 13.9448529398 10.0498756211 10.1980390272
3.15296312547 0 11.9260542188 13.1843867623 2.60472942637 6.40184399664 6.87214143805
And here is the input data:
23
18 3 0 17 14 19
19 7 8 2 1 16
8 2 0 2 1 17
14 1 10 16 1 18
18 18 17 2 0 16
1 13 14 1 15 11
17 7 2 5 9 16
2 18 7 3 10 4
0 15 10 10 0 9
5 8 8 2 10 10
14 11 15 7 10 2
3 10 12 6 13 4
11 18 20 18 15 1
6 0 14 17 0 20
6 17 12 14 11 4
17 12 14 12 19 2
16 3 17 7 20 6
9 20 9 8 9 12
7 4 9 1 18 9
6 7 16 18 0 20
0 18 7 14 0 15
0 5 10 17 10 7
8 1 20 18 13 20
Here is my answer for this input data:
10.173873024
15.6524758425
15.0
9.21954445729
17.8401898404
8.02631454901
9.97836086687
3.16227766017
5.366563146
5.366563146
7.07106781187
2.2360679775
17.0
13.9448529398
10.0498756211
10.1980390272
3.15296312547
0.0
11.9260542188
13.1843867623
2.60472942637
6.40184399664
6.87214143805
Hmm... are you using Python 3 also? Our answers are very similar; there is obviously something wrong with my algorithm, i just cant seem to figure out what or where...
No, it’s Python 2.
I think that your algorithm is sometimes false. Look carefully at the different cases.
Hi, Christopher!
As Nicolas wisely suggested, let us try to help you in debugging your program :)
I feel it would be a great boost to your bug-finding skills if you will be able to find out the cause of
the trouble.
First thing we see is that your code often gives correct results. As Nicolas said, there are several cases, so obviously for some cases your code works and for some it does not.
For example, the fourth case expects result of 9.2195... but your code tells 8.180... instead. The
difference is more than 10% so it should be good case to check.
The input for it is the following: line from (14,1) to (10,16) and the point at (1,18). You can
replay this case with simplified input of a single case like this:
1
14 1 10 16 1 18
Now, agains by Nicolas suggestion, let us draw the picture. Either with pencil, paper and ruler - or with Excel, Matlab or something like this. I use Matlab free clone named Octave:
The line is in blue and the point is marked by small red cross. It looks like in this case the
perpendicular from the point does not fall onto the segment itself, so the distance should be measured
to the closest end of the segment. The closest is (10,16). The distance therefore is:
hypot(1 - 10, 18 - 16) = sqrt((-9)^2 + (2)^2) = sqrt(85) = 9.2195
So now you can "replay" this case and print out any temporary calculations you like, to find out why your program gives you wrong result.
Could this help you? Please feel free to write for more investigation if you will not find the cause, though I believe that at your current skill level this is not very hard puzzle for you :)
I still don't get it... I'm not very good at math at all. And I can't find any information online at all. I've been searching for days now. I'm looking for a catch-all formula, but I guess there isn't one... I suppose I'll have to accept defeat for now on this one and move on.
