Let me introduce the competitive programming tool that's aimed to help you get AC more easily: ACHelper, wiki

I tried to take the best elements from Hightail, CHelper and Caide, and add project generation using CMake on top of that.

The tool itself is cross-platform and should work with any programming language and IDE that is supported by CMake (or other project generator). However, templates only for C++ for Mac (that should work for Linux as well) are implemented at the moment. Any help on Windows support is highly appreciated, more details on that here.

A screenshot of ACHelper with my AppCode IDE after the testing.

Let me know what you think.

I decided to share my implementations for the basic polygon algorithms. I see almost no problems on this topic and I hope this will change in the future.

First, let's remind the definitions we will use:

1. Polygon is a plane figure that is bounded by a finite chain of straight line segments closing in a loop to form a closed chain or circuit. These segments are called its edges or sides, and the points where two edges meet are the polygon's vertices or corners (wiki).

2. Polygon is convex if a line segment connecting any two points on its boundary lies inside the polygon. Equivalently, all its interior angles are less than or equal to 180 degrees.

3. Polygon is strictly convex if in addition no three vertices lie on the same line. Equivalently, all its interior angles are less than 180 degrees.

4. Polygon is simple if its boundary doesn't cross itself.

I will present two algorithms for each problem: one for arbitrary simple polygon, and one for strictly convex polygon, that has better complexity. The priorities in implementation design were as follows:

• handle all the corner cases, except for degenerate polygons with zero area;
• perform all computations in integers;
• optimize performance;
• write as concise and clear code as possible.

Please, let me know if you find a way to improve on any of these goals in any algorithm listed.

I get an impression that a lot of coders struggle with geometric problems and prefer to avoid them. That's not much of a surprise, considering that I couldn't find a good writing explaining the basics and giving useful advice how to proceed. Moreover, some resources obfuscate this beautiful area to the point it's despised by the readers. I'll try to change that, but first I'll mention some of the better resources:

geomalgorithms.com This is where you can start if you don't have a basic notion of a vector. Also there are more detailed explanations for some examples I'll list, but I dislike the implementations.

This post in Russian has a link to the code that's most similar to mine, with some comments (unfortunately, also is Russian)

There's this nice online judge http://acm.mipt.ru/judge that contains some important classic problems like Hard life. It's still running but looks like it was forsaken for years, because it doesn't even support C++11. I was going to submit some problems there, but I'm too used to new C++ features. Is there somebody from MIPT who can update the compilers? Thank you.

For a long time I've been upset with C++ standard input/output. First of all, I heard that fread/fwrite are much faster than everything else, and it's impossible to get good times on problems with huge input or output without using those. Secondly, it's really annoying to write formatting string and ampersands in scanf, especially with many variables to read. Thirdly, the only way to expand I/O to custom types is by overloading << and >> operators on streams, but they are the slowest. I tried to tackle all these issues in my implementation. Remember, that it's targeted for the common use case in programming contests, so it's not as flexible as one might wish.

The code is here Doesn't compile with MSVS.

I apologize in advance to everyone, who will be scrolling through this 500 lines trying to read my solutions. Also it's not advised for people without broad experience with C++ to try to understand the entirety of it (dangerous for your mental health).

Recently I've been looking for a good heavy-light decomposition code I can just copy-paste and continue to live happily. To my greatest disappointment, I didn't find one and had to write my own.

First, there's this blog explaining what HLD is http://blog.anudeep2011.com/heavy-light-decomposition/, but it doesn't contain full code. Also it uses LCA for queries, which is absolutely unnecessary and complicates things too much.

Second, there's this implementation https://sites.google.com/site/indy256/algo/heavy_light. (It has been updated, so the comment is related to old version). OK, complete working code, and it doesn't use LCA. But it has too many arrays. Way too many! Also it's mixed with segment tree code, and I'd rather separate the logic.

Third, there's this post http://apps.topcoder.com/forums/?module=Thread&threadID=796128&start=0&mc=8. So far the best looking code, but it has only LCA method and no path query handling, which is the point of HLD.

I solved the following problem http://acm.timus.ru/problem.aspx?space=1&num=2055 using approach described here http://codeforces.me/blog/entry/15296 + binary search, but my solution barely fits in Time Limit.

There are solutions 10 times faster than mine and I'm very interested what approach could they be using?

This is my first attempt at writing something useful, so your suggestions are welcome.

Most participants of programming contests are familiar with segment trees to some degree, especially having read this articles http://codeforces.me/blog/entry/15890, http://e-maxx.ru/algo/segment_tree (Russian only). If you're not — don't go there yet. I advise to read them after this article for the sake of examples, and to compare implementations and choose the one you like more (will be kinda obvious).

Segment tree with single element modifications

Let's start with a brief explanation of segment trees. They are used when we have an array, perform some changes and queries on continuous segments. In the first example we'll consider 2 operations:

1. modify one element in the array;
2. find the sum of elements on some segment.