vlecomte's blog

By vlecomte, 6 months ago, In English,

Hello!

I'm writing a book on geometry with a competitive programming approach. I've just started, so I haven't written much at all yet but I'd like to have some early feedback.

My goal is to be easy to understand and practical (quite code-oriented), but also to explain important concepts in depth and try to build intuitions / interesting interpretations, because I think I can bring some things on that front. In what I've written I feel like the "in depth" part is okay but I'm afraid the "easy to understand" part is a bit lacking.

So far I've covered complex numbers, point representation, dot product, cross products and their applications, as the first part of a "Basics" chapter. There will eventually be other chapters, covering things like sweep algorithms, algorithms on convex polygons/hulls, and especially 3D geometry, which I like a lot.

I'd like to have feedback mostly on writing style and on ways in which I can make the explanations more accessible (e.g. adding examples, figures, rephrasing, etc.), but any comment or suggested improvement is welcome. I know I've not written much but there are some concepts in there which I found tricky to explain, so there should be plenty to criticize. :)

Here's the link (I'll update it as I fix things and add sections): https://vlecomte.github.io/cp-geo.pdf

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

»
6 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Don't use complex. The book should not depend on some specific classes in standard library in one specific language. Write your own class Point and continue with it.

(conj(v)*w).Y; what the f*ck is it? Millions of people know the formula v.x * w.y - v.y * w.x and you introduce new unclear and not understandable from the first sight expression.

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    That's a good point. At the moment I'm writing this like it's a blown-out ICPC cheatsheet and it's making things less clear. I think I'll take your advice and create a point class but keep mentioning C++ hacks as asides. :)

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    +1 for not using complex. It can also be much slower than a manually implemented structure because complex may be based on complex numbers from C which use some library calls for all operations, which prevents inlining. They also try to handle some cases like NaNs and stuff; that decreases speed as well.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problem for use of complex numbers and cross product: https://icpc.kattis.com/problems/airport

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I am not eligible to give you any suggestion, but I must say, you are doing a great job. Keep going on. I would be waiting for the book. :)

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It would be really great if we had problems to practice/test our code for each topic in the book.

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

On page 18, the solution to the quadratic equation is x = 1, not x = 0. Great material by the way. Reading all the way.

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

    On page 16, I think you meant log_2(n) instead of log_2(k).

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

      Thanks a lot, those errors will be fixed next time I recompile the whole book. :)

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

Is there a list of topics you're planning on covering eventually? So far, it's been extremely useful, but has been mostly limited to elementary operations.

I know that you created a contest and you're going to put the topics covered in the problems in the contest, but I was just curious if you have a full list.

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

    I don't really have a full list. The plan is to eventually cover everything geometrical that can be useful in CP, but that's not going to happen any time soon at my current speed. ^^

    Right now I'm writing the chapter on 3D geometry and will also write a section on how to compute areas/volumes given a parametric representation of their boundaries (like in problem "Polar map"). After that my next goal is to have a chapter on all the techniques revolving around convex polygons (but I don't know when I'll have the time).