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.
Thanks in advance.