jesuswr's blog

By jesuswr, history, 21 month(s) ago, In English

Hi everyone,

I'm going to be attending the ACM ICPC World Finals this year, but my geometry skills are really bad. Geometry has always been my weakest point, and I know that it's an important area for the competition.

If you have any advice or resources that you would recommend for improving my geometry skills, I would really appreciate it. Specifically, I'm looking for a list of important geometry topics for ACM ICPC or specific practice problems that will help me get better.

Thank you in advance for your help! Please leave a comment if you have any suggestions or tips to share.

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

| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +88 Vote: I do not like it

Solve problems. Contrary to what people think, most geometry problems don't require much reference code and if you understand what you can extract from dot/cross product you're one observation away from solving most reasonable geometry problems in competitive programming.

At the very least, do understand the intuition behind "sweep line algorithms" and "radial sweep".

One thing to keep in mind is that most problems don't require any floating point calculation, so try to avoid bashing problems with copied formulas that you don't understand as much as possible, as you might be able to reorganize things in order to precision to not be an issue.

»
21 month(s) ago, # |
Rev. 4   Vote: I like it +127 Vote: I do not like it

The most important geometry topics for ICPC are:

  • 5D incremental convex hull in $$$O(n\log n)$$$ + 5D onion decomposition in $$$O(n\log^2 n)$$$

  • 3D Voronoi diagram in expected $$$O(n\log n)$$$

  • 4D online half-hyperspace intersection in $$$O(\log n)$$$ per query

  • Fast arbitrary precision floating point numbers for super precise calculations

  • Bigint as a consequence of the previous point

  • FFT, Newton's method, Burnikel-Ziegler-Verfahren algorithm as a consequence of the previous point

  • KD tree, Vantage point tree, R-tree for getting AC with $$$O(n^2)$$$ solutions

  • HTML, CSS, JavaScript. Without these you won't be able to write visual debugging tool for all that mess

  • 200+ WPM typing speed, otherwise there is no chance you will write even the first point

Have i forgot something?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Funny enough, we had a code for drawing basic shapes in our TRD. Stolen shamelessly from here. You can view SVGs in any browser, and the code doesn't require any external libraries. Not that we actually used it on either of my WFs...

»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

use vjudge workbook : https://vjudge.net/workbook

»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

SecondThread can suggest some topics and practice methodology for geometry problems.

»
19 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Read part 1 and part 2 of Handbook of geometry for competitive programmers, it's really useful.