Hey guys, I have ran across a very interesting geometry problem(at least for me). However, I am not that good at geometry and I want to ask for some help!
So the statement is the following:
We have N squares in the xy-plane given by their left bottom and right top corners. We have to count the number of visible and partially visible squares looking from the point (0,0). A square is visible(the same is for partially visible) if at least one of its segments is visible. A segment AB is visible from point O if there are no other points in the triangle OAB. So you can easily deduct that a segment is partially visible if some part of that segment is visible. Note that if a segment is visible it is partially visible too! So, anyways, I hope the problem will be interesting to solve for those have an idea and thank you in advance for your help! PS: I have an idea for full visibility but not for partial one.
Let's just give you some restrictions: N<=1000 and all coordinates given are integers and are smaller than 30 000
The basic idea is angle sweep. Sort all the corner points (4 corners of every square) with respect to O. Then check for each angle which square is visible. O(N^2) runtime.
Are you still sure in O(N^2) with respect to http://mirror.codeforces.com/blog/entry/6481#comment-119401 ?
Basic idea sweeping — ok, O(N^2) — are you sure?
It's important can the squares overlap (intersect).
If can, it looks that we need to find all O(n2) intersection points, and I'm not sure is it really possible to solve the whole problem better than O(n3) time.
If overlappings are impossible... Dealing with (similar, but simpler) problem "There are some rectangles; for each rectangle, its lower side lays on Ox; find the polygonal chain of the border of the rectangles union", sweep (along Ox) can be improved to
time, using priority queue. But I'm still not sure, whether it possible or not to use priority queue here, in angle sweeping.
There is no statement that overlapping is prohibited. Can you explain a little more about that angle sweep algorithm which can be used because I still can't figure out how one understands whether it is visible or only partially visible
It's alike http://en.wikipedia.org/wiki/Sweep_line_algorithm , but instead of vertical sweep line moving horizontally we deal with sweep ray, always starting from O, and rotating by angle.
Yes, but how does this help with solving the problem and especially the part with partial visibility. I just want someone to explain an algorithm a little more in details
I'm NOT sure are the solutions optimal enough, but...
Algorithm (A), no sweep at all: consider all squares' vertice, find all edges' intersections; sort them all together by angle; for each range between neighbor event point, find the nearest to O segment.
It's O(n3) time and O(n2) memory.
Algorithm (B), angle sweep: consider all squares' vertice; sort them by angle; let's call the vertice static event points, and let's call other edges' intersections dynamic event points. Going from each event point, we calculate nearest dynamic event point and choose either it, or next static event point (what becomes earlier).
Also, maybe you'll find useful sections 7.4 and 7.5 of (Russian-language) book Порублёв Ставровский Алгоритмы и программы Решение олимпиадных задач.
The main thing sweeping helps in this pair of algorithms is memory usage: O(n2) for pre-calculating all intersections, O(n) for finding the intersections dynamically. But, maybe (I'm not sure) sweep with better status structure can guarantee even smaller run time.
Dude! I get the sweep, but how do you check visibility?!?! I understand how to find intersections but how do you understand when a segment is fully or partially visible. An intersection within an angle doesn't mean that segment is not visible. Now I don't want a big discussion or arguing because I'm not that much into geometry so please if someone knows a solution which is going to output number of visible and partially visible squares please just explain it accurately. I'm not worried about intersections or whatever. :)
Consider as sweep status "*array of all segments in current sector, ORDERED BY distance from O*". Segment is partly visible from O iff there is a non-zero-length range between event (static or dynamic) angles, when it's the 1st in sweep status.
Where am I wrong? Maybe it's not the best possible sweep status, and leads to not the most effective solution. But why is it incorrect?