project euler problem 165

Intersections

This is a good exercise to learn a little bit computational geometry.  I checked my old code. It takes 3.9 seconds to get the answer. I feels that my code is too slow but did not figure out how to speed it up. 

I checked the discussion, Robert_Gerbicz gave me an idea how to optimize. It is very simple, avoid using set or map when possible.  I followed his idea and removed set in my code, the run time is reduced to 1.4 second.

The set and map container are notorious in c++, probably because there was no hashset or hashmap available when STL was first published in 1990s.  I had a lot of experience that set and map caused a lot of coding and performance issues.

project euler problem 102

Triangle containment

This problem is great! I used very complicated logic in my code. I got the correct answer after I fixed one tricky bug in my code. Then I checked the discussion thread. I found two interesting algorithms. First, how to calculate the area of the triangle given the coordinates of vertices. Second, how to solve this problem efficiently. I feel awful that I missed these algorithms for more than a year!