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.
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.
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?
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...
use vjudge workbook : https://vjudge.net/workbook
SecondThread can suggest some topics and practice methodology for geometry problems.
May I humbly suggest mastering the basics of Convex Hull and All Point Pairs.
Convex Hull Tricks: https://mirror.codeforces.com/blog/entry/79862
All Point Pairs: https://mirror.codeforces.com/blog/entry/79928
Read part 1 and part 2 of Handbook of geometry for competitive programmers, it's really useful.