k790alex's blog

[COJ] 2067 — City Houses, How to solve it?
By k790alex, 11 years ago, In English

Hi, in a past contest I meet this problem: http://coj.uci.cu/24h/problem.xhtml?abb=2067 I couldn't solve it and affter I study some algorithms, I saw again and I tryed to solve it but I couldn't do it again. I think I need to use Line Sweep to solve it but I wonder if anybody knows an easier way (I don't know too mucho about line sweep). Thanks and sorry for my english.

  • Vote: I like it
  • -11
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 5   Vote: I like it +13 Vote: I do not like it

For a given point (x1, y1), it is necessary to find the closest point to it (x2, y2). The are four cases:

  1. x2 >= x1 and y2 >= y1

  2. x2 >= x1 and y2 <= y1

  3. x2 <= x1 and y2 >= y1

  4. x2 <= x1 ans y2 <= y1

Let's see how to solve the case #1.

Since x2 >= x1 and y2 >= y1, then dist(p1, p2) = |x2 — x1| + |y2 — y1| = x2 — x1 + y2 — y1 = (x2 + y2) — (x1 + y1).

As you can see, the best option in this case is to choose the point such that x2 + y2 is minimum. This can be solved using a data structure supporting the following two functions:

query(Y): finds the point (x, y) such that y >= Y and x + y is minimum among all the points in the structure.

add((x, y)): adds the point (x, y) to the structure.

An example of such data structure is a Binary Indexed Tree.

Let p be the input points:

sort p in decreasing order of x coordinates

foreach point in p
    answer[point] = query(point.y)
    add(point)

The other three cases can be solved in a similar way.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What you mean it's a 'Quad Tree', I implement it but it gives me TLE (I using java), a friend of me solved it using 2D-Tree with 'Quick Select' algorithm for building the tree.

    → Reply