Return to Volume I Explanations

 Problem 149 - Forests, Explanations 

Algorithm

Process only the 300 nearest trees. There's no reason we will suddently see a tree at three kilometers!

Order them by distance to the observer.

For each tree, calculate the coordinates of the extremities. That's the intersections of the circle of the tree with the line going through the center of the tree orthogonal to the line joining the origin and the center of that tree.

For each tree, process all further trees and darken all trees behind it. A tree B is behind a tree A if :

  • The segment joining the extremities of A intersects at least one of the segments joining the origin and the extremities of B.
  • Or, the angle between one of the extremities of A and one of the extremities of B is smaller or equal to 0,01 degrees.

    Count all visibles trees.

    Trick

    You can split the trees into four quadrants to speed up. A North-West tree will not shade a South-West one.

    A partially shaded tree can shade other trees behind it.

    0,01 degree is PI/18000.

    The forest is infinite by all its dimensions.

    You can take a look at my geom basis.

    If you are in trouble with the multi-entry input, read my how to read input.

    Additional Input

    149.in

    Additional Output

    149.out

    Problem

    The saying ``You can't see the wood for the trees'' is not only a cliche, but is also incorrect. The real problem is that you can't see the trees for the wood. If you stand in the middle of a ``wood'' (in NZ terms, a patch of bush), the trees tend to obscure each other and the number of distinct trees you can actually see is quite small. This is especially true if the trees are planted in rows and columns (as in a pine plantation), because they tend to line up. The purpose of this problem is to find how many distinct trees you can see from an arbitrary point in a pine plantation (assumed to stretch ``for ever'').

    picture23

    You can only see a distinct tree if no part of its trunk is obscured by a nearer tree--that is if both sides of the trunk can be seen, with a discernible gap between them and the trunks of all trees closer to you. Also, you can't see a tree if it is apparently ``too small''. For definiteness, ``not too small'' and ``discernible gap'' will mean that the angle subtended at your eye is greater than 0.01 degrees (you are assumed to use one eye for observing). Thus the two trees marked picture169 obscure at least the trees marked picture175 from the given view point.

    Write a program that will determine the number of trees visible under these assumptions, given the diameter of the trees, and the coordinates of a viewing position. Because the grid is infinite, the origin is unimportant, and the coordinates will be numbers between 0 and 1.

    Input

    Input will consist of a series of lines, each line containing three real numbers of the form 0.nn. The first number will be the trunk diameter--all trees will be assumed to be cylinders of exactly this diameter, with their centres placed exactly on the points of a rectangular grid with a spacing of one unit. The next two numbers will be the x and y coordinates of the observer. To avoid potential problems, say by being too close to a tree, we will guarantee that tex2html_wrap_inline260 . To avoid problems with trees being too small you may assume that tex2html_wrap_inline262 . The file will be terminated by a line consisting of three zeroes.

    Output

    Output will consist of a series of lines, one for each line of the input. Each line will consist of the number of trees of the given size, visible from the given position.

    Sample input

    0.10 0.46 0.38
0 0 0

    Sample output

    128

    Return to Volume I Explanations