UVa problem 10865: sample algorithm

To solve problem 10865 (Brownie Points), one can imagine the plane divided into 4 quadrants like in Figure 1.


Figure 1. Plane divided into 4 quadrants.

In Figure 1, Stan draws his vertical line while Ollie draws his horizontal line so that the two lines intersect to form the center point with coordinates (x0, y0).

The center point corresponds to the middle of the input sequence provided by the user. Please refer to Figure 2 for an illustration.


Figure 2. The middle point corresponds to the center point.

In Figure 2, x0 is equal to 1 and y0 is equal to -3.

In Figure 1, the plane is divided into 4 quadrants: pp, pn, np and nn. The quadrant pp corresponds to that portion of the plain that is above and to the right of the center point. The quadrant pn corresponds to that which is below and to the right. The quadrant np corresponds to that which is above and to the left. The quadrant nn corresponds to that which is below and to the left.

So given a random point (x, y), we check to which quadrant it belongs to by comparing x against x0 and y against y0. For example, for the first point in Figure2 (3, 2), x > x0 since 3 > 1, and y > y0 since 2 > -3. As such the point (3, 2) is to the right and above the center point (1, -3). Hence it belongs to the quadrant pp.

For each point then, we determine the quadrant to which it belongs. Then we sum up the number of points belonging to each quadrant. Stan’s score is simply the number of points within pp and nn, while Ollie score is the number of points within pn and np.

Note also that if x is equal to x0, or if y is equal to y0, we do not accumulate the point into the total of any quadrant, as the problem states that crossed brownies do not count.