Editorial for COCI '06 Contest 6 #6 Prostor


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

We'll say a rectangle with coordinates (x1,y1,z1,x2,y2,z2) is of type X if it is "thin" in the x dimension, i.e. if x1=x2. Rectangles of types Y and Z are similarly defined.

Define a function count(X,Y) that does the following:

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 count(X,Y)+count(Y,Z)+count(Z,X).

Algorithm for count(X,Y):

Imagine that the y coordinate represents time. Let time flow and observe the (x,z) plane representing space at some moment in time. Rectangles of type X become vertical line segments while rectangles of type Y remain rectangles.

Rectangles of type X have some positive lifetime (because y1<y2), while rectangles of type Y exist at only one instant (because y1=y2).

As time flows, three types of events can occur:

  1. A type X rectangle starts
  2. A type Y rectangle starts and ends immediately
  3. 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 (x1,y,z1,x2,y,z2) of type Y comes to life, answer the question "how many vertical line segments in a set intersect the rectangle (x1,z1,x2,z2)?".

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 (x1,y,z1,x2,y,z2) of type X comes to life, answer the question "how many vertical line segments in a set intersect the (degenerate) rectangle (x,z1,x,z2)?".

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: O(NlogN+Nlog2M) where M is the largest allowed coordinate (999 in this problem).


Comments

There are no comments at the moment.