Hello, codeforces!
Because after Round #507 sad men in suits visited me in my flat, this time I won't write about any task from the future. Instead, this blog will be about my own trick. I said "my own," but probably some of you have already heard about it or even figured it out, but I've developed it by myself, so I consider it as my own.
In particular, it's GEOMETRY TIME!!!. But please, don't escape already. I also don't like this topic so much, that's why I really like this trick. Let me tell you a story from one onsite Polish contest, which took place a few months ago. I was thinking about one of the problems, and I've figured out that I had to do some binary-search (on doubles) and then check if a set of half-planes has a non-empty intersection. The answer would tell me in which direction should I turn in the binary search.
Firstly, I grabbed my head, because I've never written an intersection of half-planes. I had my acm library with Errichto's codes inside, but my knowledge in usage of his part was limited to copy-pasting FFT and Rho-Pollard. Not only I, but also Swistakk figured out the thing about binary search and was trying to intersect half-planes normally, but he failed (we still aren't sure why, probably because of precision issues). Then, I reminded myself a task from eliminations to BubbleCup 2017 (you can submit here), which I solved with the mentioned trick.
So, the trick goes as follows. Imagine a situation when you need to check if an intersection of a set of half-planes is empty or not. For simplicity, let's assume that there are no vertical lines in the input. So each half-plane tells us either "you have to be below this line" or "you have to be above this line." If there is no half-plane which tells us "you have to be below," then for every x we can find some y which is above every line, so the answer is YES (intersection is non-empty). This same applies to no half-plane which tells "you have to be above." From now, at every x we are limited both from down and from up.
Let's consider an upper convex hull of half-planes (this which tells us "you have to be below this"). Don't calculate it, just focus on the fact that it exists. It looks like this:
It might be confusing, but I'll call it "upper convex hull" anyway, mostly because it's above "bottom convex hull." :) The red area is an intersection of half-planes. It has one important property. It is... convex. Yea, it's not a big achievement to notice it. Next great observation: the bottom convex hull is convex. Not a big deal again. So, here comes the next one: the difference between upper and bottom convex hulls in convex. Yea, yea.. wait, what? The situation isn't so trivial this time. It's convex because of some mathematical laws. I'll skip the details, it's easy to notice it/believe in it. Buuuut, what does "difference between upper and bottom convex hulls" mean? For fixed x it means the difference between y of the upper convex hull and y of the bottom convex hull at this x (because we can assume that both convex hulls are graphs of proper functions).
Black and blue lines mean different types of half-planes. The green area denotes their intersection, and the red area denotes... Well, mentioned "difference" doesn't have to be positive. More, if the intersection of half-planes is empty it even has no places where it is positive, so the red area denotes its negative equivalent. The longer the vertical red line at some point is, the less (more negative) the difference is. Here's an example of a test where the intersection is empty:
So, the set of half-planes has non-empty intersection if and only if there is x for which the difference between upper and bottom convex hulls is positive. We want to find such x as a proof that it exists. How to do it? We know that this "difference" function is convex, so it's also bitonic (firstly increases and then decreases). Hmmmmm, bitonic functions, what do we know about them? They have important usage in competitive programming: ternary search! As we want to find x with the positive difference, let's find x with the maximum possible difference and check if this difference is positive.
How to calculate the difference for fixed x? Just find minimum on black lines (according to the picture), maximum on blue lines and subtract them.
"For simplicity, let's assume that there are no vertical lines in the input." Yea, of course, there are vertical lines in the input, as always... What can we do with them? In ternary search, we start with some initial interval, let's say ( - inf, inf). Of course, it's not real infinity. It's infinity like 1018, or something similar. Vertical half-planes should just cut our interval and make it smaller. If the interval is still non-empty after considering all vertical half-planes, we do the ternary search (only in this interval), if it's empty, the answer is NO.
Unfortunately, I'm not an expert in epsilons, but of course, I know basics. That's why I was so happy that I'm doing this trick as "a check" in the binary search. If due to precision I made a wrong decision, then probably I did it close to the border that I am looking for with the binary search, and from now I'll keep getting closer to it.
Anyway, I was forced to use epsilons in my code to make it work. As I'm not so good, I won't write about my intuitions, because they might be incorrect. Using an opportunity: is there anybody who feels that he is really good at handling with doubles precision and wants to write some tutorial about it? I'm sure that it'll be very useful for the community! :P
So, now we know how to check if a set half-planes has an empty intersection or not (with concise and easy code). It might be not so useful because some of you would take the challenge and try to intersect half-planes normally. What if it comes to half-spaces? It's harder to calculate convex hull in 3D than in 2D. What with the described trick? It turns out that it still works! Function f(z) defined as "the longest possible segment (with possibly negative length) parallel to OX with given z and for optimal y" is also bitonic (I'll skip the proof), so we can do two nested ternary searches.
So, this is the end. I hope that you found this blog useful. If you want to try something hard, you can try to solve this Errichto's task. If you'll get stuck, there is a nice Um_nik's code, which (if I understand it correctly) uses this trick. I hope that he won't be mad at me for referring to his code. Also, feel free to discuss this task in the comments. See you next time! :D
Oh, wait, wait, wait, there is one more thing. As this is already my fifth blog and it looks that I won't stop writing them, I want to thank my friends (Errichto, Swistakk, Marcin_smu and mnbvmar) very much, mostly for helping me make my English better, catching typos and of course for their opinions about solutions and tricks. Blogs aren't very short, so you guys should know that I'm really thankful for your patience!
