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.

UVa problem 10865: sample code

001 #include "stdio.h"
002 
003 int main() {
004   char   line[100]
005        ;
006   int   i
007       , x
008       , y
009       , x0
010       , y0
011       , num_points
012       , grid[200000][2]
013       , middle
014       , pp
015       , pn
016       , np
017       , nn
018       , stan
019       , ollie
020       ;
021 
022   while (fgets(line, 100, stdin)) {
023     sscanf(line, "%d", &num_points);
024 
025     if (num_points == 0) {
026       break;
027     }
028 
029     for (i = 0; i < num_points; i += 1) {
030       fgets(line, 100, stdin);
031       sscanf(line, "%d %d", &x, &y);
032 
033       grid[i][0] = x;
034       grid[i][1] = y;
035     }
036 
037     middle = num_points >> 1;
038     x0 = grid[middle][0];
039     y0 = grid[middle][1];
040 
041     pp = 0;
042     pn = 0;
043     np = 0;
044     nn = 0;
045 
046     for (i = 0; i < num_points; i += 1) {
047       x = grid[i][0];
048       y = grid[i][1];
049 
050       if (x == x0 || y == y0) {
051         continue;
052       }
053       else if (x > x0 && y > y0) {
054         pp += 1;
055       }
056       else if (x > x0 && y < y0) {
057         pn += 1;
058       }
059       else if (x < x0 && y > y0) {
060         np += 1;
061       }
062       else {
063         nn += 1;
064       }
065     }
066 
067     stan = pp + nn;
068     ollie = np + pn;
069 
070     printf("%d %d\n", stan, ollie);
071   }
072 
073   return 0;
074 }