CrazyDiamond's blog

By CrazyDiamond, history, 5 years ago, In English

Hi Codeforces! I'm currently training to go to the ICPC World Finals and after yesterday's Latin American Regional I realized something: I know nothing of Geometry!

Well to be fair, I know a few things here and there because of highschool and college, but my understanding of it is such a chaotic mess that I find it really to apply that limited knowledge in contests.

I'm trying to fix that but I don't really know how to start, so if someone could give me advice on how to start learning geometry from scratch and how to properly move on to harder things in competitive programming (geometry-wise) I would really appreciate it. Moreover, if you could recommend geometry books that you think could help me I would be even more thankful :)

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

»
5 years ago, # |
  Vote: I like it +51 Vote: I do not like it

Assuming you're talking about analytical geometry and not rare things like that D in AGC: Library functions are a must. A lot of fails in geometry problems are due to not knowing a correct formula or missing special cases and standard stuff to compute like intersection of segments appear very often. There's just a few algorithmic ideas (e.g. "rotating calipers") and they aren't all that hard.

A common trick with non-convex inputs is reduction to convexity. If you can replace a polygon or set of points by their convex hull, it has some nice properties that you can use.

Apart from that, play around with drawing everything related to these problems to get a feel for it. That's one nice thing about geometry, you can gain a lot of insight into it with pen and paper.

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

Not really an answer, but the tip that helped me a lot (maybe you know it already): use matrices to formulate and solve all necessary equations. That makes math much cleaner and handling various cases (like number of solutions) easier quite a bit.

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

    Your idea sounds really interesting. Can you provide some nontrivial examples of using matrices in computational geometry?

    I cannot come up with any way to use matrices in problems with circles or areas.

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

      You got me, I did not say I was good with circle problems m_m

»
5 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Hey, I like this book. https://vlecomte.github.io/cp-geo.pdf it explains a lot of things and has many codes explained. Also there are some interesting post in codeforces about computational geometry. Maybe you can find them and learn from them. Good luck.

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

You could create a template with basic operations over lines, circles, polygons, segments and points. If you create it by your own you will learn a lot, then you may try to test and improve it.

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

There are a couple of things you have to know:

1) how IEEE floating-point works, and especially, when you can use a naive formula and still get the exact answer, vs. when you have to implement formulas using integer/rational arithmetic;

2) a few basic geometry formulas, for example:

  • segment-segment intersection
  • segment-circle intersection
  • polygon area
  • is a point inside a polygon?
  • lines tangent to two circles
  • circles tangent to various things (three points; three circles; two circles and a line; etc)

Fair warning: many formulas you'll find online are not fully correct or robust (they ignore some corner cases, e.g.). It's worth looking up high-quality solutions to these basic queries (or even better, if you have time, deriving them yourself), writing them down in your reference documents, and then practice using them.

3) a few basic algorithms and techniques, for example:

  • angle sweep
  • convex hull
  • rotating calipers

These, combined with careful thinking about corner cases and some on-the-spot derivation, will get you 75% of the way there when it comes to geometry problems. For example, "Airport Construction" from WF 2017 requires only the basic formulas and some small insights (i.e., that the longest runway must pass through two polygon vertices), but is hard because you have to be very methodical and precise to solve the problem robustly (handling cases like multiple colinear vertices, non-convex island shapes, runways coincident with some of the island edges, etc.)

Of course, there are plenty of other algorithms that show up every now and then, and it's cliched but true that the best way to get better at geometry problems is to simply practice more problems, taking note of any algorithms or formulas you wish you would have had in advance.

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

    when you can use a naive formula and still get the exact answer

    For practical purposes never. It's better to assume everything is imprecise than to pointlessly get WA.

    when you have to implement formulas using integer/rational arithmetic

    When the alternative fails or is way more difficult, obviously.

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

      Of course you don't simply guess and hope for AC; that's not my suggestion. Rather, there are many times you can (provably!) safely use floating point, which is then much less of a hassle then implementing e.g. a rational number class. One example is, again, "Airport Construction."

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

        It's more like there are very few times when you can't safely use floating point. In CF or other contests with full feedback, it's worth considering because you can fail systests or get hacked, but in ACM? Meh. Try floats with eps-comparisons, if you get WA then start thinking if it was a mistake.

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

I learnt a lot from this blog

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

You might want to start with the Geometry section of this website.