0
$\begingroup$

I am working on Project Euler Problem 102 and I thought I had a solution, but it seems I do not.

Now, don't give me the solution. I know I'm on the right track. What I want to know is why my method proved incorrect.

Here is my algorithm in sudo-code:

theta1 = angle of line (0, pt1) theta2 = angle of line (0, pt2) theta3 = angle of line (0, pt3)  max angle = max(theta1, theta2, theta3) min angle = min(theta1, theta2, theta3)  if (max angle - min angle > 180)     Yes! contains origin else     No! does not contain origin 

Why is this not correct? If the origin lies inside the triangle then the rotation of a line from the origin to each of the points would yield an angle of more than 180. If the origin lies on one of the triangle sides then (max - min) would be 180 exactly, right? if the origin was not inside the triangle then (max - min) would be less than 180, etc.

I can see this in my head, but I'm obviously missing something. What am I missing?

  • 0
    **Hint:** There is a hugely easier approach to the problem.2011-11-19

2 Answers 2

0

It's probably because you must make sure your computations occur with the right calculations, i.e. it might happen that max - min > 180 and your triangle does not contain the origin, for instance with the triangle A=(1,1), B=(1,-1), and C=(2,0). The min angle will be 0, your max angle will be 315 degrees but it doesn't contain the origin. So... you're "not" on the right track, but computing angles is definitely a good idea.

Small hint : Try computing angles that consider the origin in their computation, for instance angle AOB. You might get more useful information there. If you want a bigger hint just ask.

Hope that helps,

0

As noted in a Bresenham's explanation answer, one form of line equation is f(x) = dy*x - dx*y + c, with f(x,y) zero for points on the line, positive for points on one side of it, and negative for those on the other. If, for each pair of triangle-points, the origin is on the same side (of their line segment) as the remaining point, what can you conclude?

Note, all of dx, dy, and c can be computed in integer arithmetic without using any divisions or trigonometry, which may help you avoid some problematic cases.