Happy New Year everyone !
I want to direct your attention to tutorials . They are not as detailed as they are needed . Last contests' tutorials (Good bye & CR#221) look like written in 30 minutes . Some of problems are explained well , but others are hard to understand even after reading more explanation in comments . For example : "221 Div1 C" & "Good Bye E" tutorials of this problems are just hints in my opinion .
I want to ask authors of this problems to update tutorial and write it more detailed . I am lazy to analyze other contestants' codes as they are in writing tutorials .
Happy New Year to you!
I've read the explanation for Good Bye E and I agree with you that it's really bad. But this comment clarifies the solution pretty well.
If you still don't understand the solution, you should just ask for a more detailed clarification, but not in the style of this post (IMHO).
Anyway, if you try hard to do something, but don't succeed and ask for help, it's very likely that people will help you. But if you're lazy and don't want to work, it's your and only your problem.
The solution of problem E wasn't not clear for me after reading that comment too . I have read it before writing this post .
I can find out the solution after analyzing the codes , if I spend much time . Tutorial exists to use time effectively .
If they are writing tutorials such , that I must try hard to understand it myself , just don't call that post tutorial and everything will be okay .
I don't understand your problem. In GoodBye E the only thing you have to do is to find an intersection of some polyplanes, which is a well-known problem and can be solved even in O(n log n) time, but easier solutions in O(n^2) was also sufficient. O(n^2) solution is rather straightforward, but for me, still painful in implementation :P. In 221 Div1C at the first moment I didn't understand the solution, but this was only because it was written in bad English. This problem was very clearly explained in comments — for example here: http://codeforces.net/blog/entry/10084#comment-155446 .
Finally understood 221 Div1C solution , my fault . But still don't know how to solve GoodBye E even in O(N^2) :(
Problem: We have lines l1, l2, ..., ln and we want to construct "downward convex polyline" (I hope this is a good expression for that ; p) of every prefix l1, ..., lk. Firstly sort them by their inclinations from those "going down fast" to those "going up fast" and nextly we will do it for all k=1, 2, ..., n independently. After sorting them by inclinations algorithm is essentially the same as algorithm to build a convex hull. Note that such a downward convex polyline has 2 infinite parts — left one is a part of a line with the smallest inclination and right one is a part of a line with the greatest inclination. When adding a new line a part of it will be the right infinite part of this polyline. This allows us to forget about some last lines we added and add this new line. Remember that one of segments will probably be divided into two parts and we should keep left part and forget about the right one. Whole polyline should be kept as a sequence of consecutive points in this polyline in a stack which supports popping last element and adding new one in amortised constant time, which results in O(n) algorithm. Now you're ready to implement E's from last two contests — Good Bye and also #222 :P.
Oh, and when computing an intersection of polyplanes which don't have to be "above line" such as that I described in last post, you can divide them for those polyplanes which are above corresponding line and those which are under, use that algorithm I described and merge this two intersection (but keep in mind that resulting intersection can look in a various ways! — it can be infinite!).