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
    I don't know if it's just a typo in your code but I see "man angle - min angle", which could cause problems if this was in your code.2011-11-19
  • 0
    Thanks. Fixed it. This was not an issue in my code, though.2011-11-19
  • 0
    does `angle of line` measure the angle from the positive x-axis?2011-11-19
  • 0
    Not an answer, I have poor intuition about angle of line $OA$, presumably the angle we must rotate the positive $x$-axis so it coincides with ray $OA$. Maybe if one point of the triangle was on the positive $x$-axis, my geometric intuition would work. Or if we were working with angles, or other stuff, that are more *geometric*: determined by $A$, $B$, $C$ and some additional point $P$ (in your case the origin) and more or less invariant if the configuration determined by the $4$ points is shifted, rotated, even squeezed. Angle with positive $x$-axis is not like that.2011-11-19
  • 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.