SecondThread's blog

By SecondThread, history, 5 weeks ago, In English,

AlgorithmsThread Episode 7: All Point Pairs

Hi everyone! I just published Episode 7 of AlgorithmsThread, which talks about processing all pairs of points, while keeping the rest of the points sorted in a helpful way. I talk about the following problems in it:

  • Biggest Triangle in a set of points
  • Smallest Triangle in a set of points
  • Number of pairs of non-intersecting triangles
  • Minimum Area Quadrilateral in a set of points

I find this to be a really helpful trick that isn't super well known, so feel free to check it out if any of these sound like things you want to learn!

Problem Links:

Feel free to post any questions below!

 
 
 
 
  • Vote: I like it
  • +145
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks for sharing the gem.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by SecondThread (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What are the etymologies of the names "Algorithms Dead" and "AlgorithmsThread"?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Also, wanted to add that I watched some of this video and thought it was well-presented! I liked how you explained the motivation behind some of the ideas & used drawing extensively. What software/hardware are you using for the drawing? (I assume you're using OBS for the recording?)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Derived from Algorithms Live and his handle name I guess.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh cool, thanks! I hadn't heard of Algorithms Live before, but I see the connection now. :P

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yep, originally it was Algorithms Dead as a pun on Algorithms Live. Then I changed it to AlgorithmsThread because that sounds a bit cooler I think.

»
5 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Here's another good problem on this technique: 1019D - Large Triangle

I wrote up an explanation of that problem here: https://codeforces.com/blog/entry/61144