Investigating the Torricelli point of a triangle
This is undoubtedly the most difficult problem in the first 150 problems. After it was posted for more than 6 years, only less than 1200 people solved the problem. This problem is created by hk. If you often goes to the PE forum, you can not miss his posts. He is very smart and pretty tough :).
Probably the most difficult part is to parameterize the triangles. Wikipedia is our good friend. After that part is done, it is a pure computer science problem. I do not have very good solution. My old code used multimap. It needs 4 second I rewrite the code and used unordered_map (hashmap). Now I only need 0.6 second to get the answer.
Update: in the discussion thread, lzw75 asks the answer for p+q+r <=1e7, I found that my notebook can not run. It costs too much memory. I then checked my code and found that I am too careless about my data structure. I changed the code a little bit. Now I can run it. It takes 71 seconds. For p+q+r<=120000, it only takes 0.2 second now.
No comments:
Post a Comment