Hardly worked on the following problem(statement in russian, registration is required) but without any success, help plz:
On positive axis (x>0,y>0) Given N blue triangles and M red points. Triangles have one property: they share common vertex at [0,0].
For each triangle we must determine is there at least on red point inside it.
Constraints:
- coordinates are integers between (0,10^9]
- N<=10^5
- M<=10^5
- TL = 2sec
I understand some sort of optimization needed : sweep line or segment tree, but I couldn't figure it out
Do you know how to solve or link to the similiar problems. I would really appreciate.
UPD: You can't probably solve this problem if you don't know segment tree or convex hull or ternary search or if you don't know how to use them together!
Thanks in advance.
I think the following idea can help. Let's sort our red points by angle, and also let's sort the sides of the triangles (which are incident to the vertex (0,0)). Let's also add to the set of blue points 2N distant points which are situated on these sides. Then we can use an idea similar to sweeping line: we'll turn around the point (0,0) and build a convex hull of blue points, including distant ones. When the triangle "starts", we start building a new convex hull for this triangle; when the triangle "finishes", we obtain a convex hull for it and can find an answer using ternary search on this convex hull. Then if we have a "current" triangle, we need to merge the convex hull for the "just finished" one with a part built for "current" one. If I'm not mistaking, all those operations can be done in O(log n) time...
Could you please reformulate problem statement regarding ternary search as a separate problem
Because I know problem of checking point in convex polygon using binary search (in logN time, it is not applicable because we have M points to check)but what you've said is unknown to me.
Thanks!
Well, as I guess our part of convex hull (which will be obviously started and finished with a certain "distant" point) can be presented as a convex piecewise linear function, and we just have to determine if it does intersect with a linear function (that is, the third side of the triangle). So, I think ternary search is applicable here. As building convex hull for K points needs O(KlogK) time, and we don't "disturb" any point twice, this part will be O(NlogN). A merge of two convex hulls can be done also in logarithmic time, and we do it at most 2N times. The only point is "unmerging" of convex hulls, but I think if we "precalc" the convex hulls for each sector, we can avoid it.
Yes, cool!
We kinda need to keep the state of the convex hull!
But I think we might face two troubles:
— If we precalc convex hulls we fail the memory limit
— In worst case O(N) points may be added or deleted to our convex hull when triangle "finishes"
I've read the idea of DryukAlex and didn't exactly understand, what did he mean, so I'll explain my own solution. Btw, after fixing bugs in it, which lead to TLE4, now it gets Check Failed.
If we needed to check if there exists a point inside a sector, it'd be much easier (the solution would be just to convert all points to the polar coordinates, sort them in an increasing order by angle θ and find minimal radius on some intervals).
But in our case we have not sectors, but triangles. Instead of checking minimal radius on an interval, we need to check if there exists a point on this interval that lies on a half-plane that corresponds to the inside of the triangle
Let's notice that if such a point exists, there exists a point on the convex hull of points on the interval that lies inside the triangle. Also, it's sufficient to know only the "lower" part of the convex hull (I mean: the part that is visible from the origin). If we know it, we can check if there exists a point inside the triangle just using ternary search.
We can't store convex hulls for all the O(K^2) intervals. But we can just build an interval tree and for each interval store its convex hull. This will take us an O(K * log K) time and memory, since for a set of sorted points a convex hull can be built in a linear time.
And when we need to perform a query, we just descend the interval tree and check all the intervals our interval is composed from. It will take O(log^2 K) time (O(log K) intervals and a ternary search in O(log K) on each of them).
My explanation can still be unclear, so I attach a picture that seems to help you and my code.
Just to make clear: on every vertex in segment tree you don't have some compressed info, but all vertices that is in convex hall of this interval?
Yes, you're right.
Well, then, one thing is for sure! This is awesome!
Well, my idea was almost the same, except for using not segment tree but merge operations of convex hulls. Of course, at first we have to sort the triangles for the angles of their right side and then turn our "sweeping line". If I'm not mistaken, this gives an O(NlogN) solution. But I can't understand, why in your solution the composition of neighbouring convex hulls will also give a convex hull. Don't we need to remove any "unnecessary" vertexes?..
Well, if we consider "unnecessary" vertices, it doesn't matter for the correctness of our solution. We just use the obvious fact that if a vertex lies on a convex hull of a set, and this set is composed of several other sets, then it lies on a convex hull of one of them.
Yes, you are right. I need to merge the hulls, because I use one "big" ternary search, but you don't need it.