Editorial for COCI '06 Contest 6 #6 Prostor
Submitting an official solution before solving the problem yourself is a bannable offence.
We'll say a rectangle with coordinates
Define a function
Select all rectangles of types X and Y and count how many pairs of rectangles there are such that at least one of them is of type X and they share a point.
The overall solution is
Algorithm for
Imagine that the
Rectangles of type X have some positive lifetime (because
As time flows, three types of events can occur:
- A type X rectangle starts
- A type Y rectangle starts and ends immediately
- A type X rectangle ends
We sort the events by time and process them one by one.
To count all pairs of rectangles sharing a point, such that one is of type X and another is of type Y, we need to, whenever a rectangle
To count all pairs of rectangles sharing a point, such that one is of type X and another is of type X, we need to, whenever a rectangle
Both questions can be quickly answered if we store the starting and ending points of all vertical segments in a 2-dimensional Fenwick tree (a la IOI 2001 mobiles).
Time complexity:
Comments