Project Euler/Problem 102

The solution to Problem 102 came fairly quickly - it comes from comparing cases where the triangle does contain the origin, to cases where the triangle does not.

We start by noticing the pattern, that if all the points are clustered on one side of the graph, there is no way it will contain the origin. Same thing with top and bottom. From this we deduce that we need the x values or the y values or both to span the origin. Start by assuming that ONLY the x points straddle the origin, that is, that if we have two points on one side of the origin, we have one point on the other. Now we actually "draw" the two legs of the triangle that would fall on either side of the origin. Given the endpoints of the triangle, we can determine the equation of the line using the point-slope formula. Finally, we find if these fall on either side of the origin by comparing the signs of the y-intercepts.

Implementing this solution required some somewhat complicated logic to decide which points to draw which lines from and to. I'm not sure how to avoid this. Here are the decisions and the decision criteria involved:

• First, determine the "parity" of the triangle - how many points have positive x values, minus how many points have negative x values. If the parity is not 1 or -1, the triangle cannot contain the origin.
• One of the endpoints will be used in both lines that we draw. This is the point whose x value has the opposite sign as our parity.
  • If the parity of the triangle is positive (meaning there are two endpoints on the positive x side) we should use the negative x endpoint for both of our lines
  • If the parity of the triangle is negative (two endpoints are on negative x side) we should use positive x endpoint for both lines
• The other two endpoints should each be used once in each of the two lines.