PNOI 2k8 Problem C: Checking Collinearity

Problems from PNOI2008

Type: geometry
Difficulty: easy to medium, tedious

This problem was easier before editing: I suggested to keep all the coefficients as integers, so that there would be less problems with the precision of floating-point numbers. It would have been much more straightforward if the lines were given in standard form (i.e., the form y = Mx + B) instead of general form (i.e., the form Ax + By + C = 0), even if that required a special case for vertical lines, which have the form x = C. This also added the process of removing the common factors of A, B and C, and the output format considerations.

In geometry, we find that two points can determine a line, and a third point is collinear with the first two if it falls on the determined line. We get the first two points (ax, ay) and (bx, by) and determine the equation of the line that they determine.

In standard form, M = (by - ay) / (bx - ax) is the slope of the line, and B is the y-intercept of the line (and not the same B in the general form). We can determine the general form of the equation of a line from its standard form: y = Mx + B has general form Mx - y + B = 0. To make both coefficients integers, we multiply both sides by the denominator of M, so, using the formula for the slope above, we have(by - ay)x - (bx - ax)y + B(bx - ax) = (by - ay)x + (ax - bx)y + C = 0. The value of C is determined by plugging in a point of the line, say (ax, ay) into the equation, i.e. C = -(A * ax + B * ay) = (ay - by)ax + (bx - ax)ay. We choose, however, to remove the common factors of A and B before determining C.

First, to remove the common factors of A and B, we have to determine their greatest common factor (GCF), so we can divide them both by their GCF and they will have no common factors, i.e. be relatively prime.

Euclid, father of geometry, also has an efficient algorithm that determines the GCF of two positive numbers, a and b. He noted that the GCF of a and b is also the GCF of a and the remainder when dividing b by a. Noting that the GCF of 0 and any nonzero number is the number, Euclid's algorithm can be implemented in a function:

int gcf(int a, int b) {
  if (a < b)
    swap a, b;
  while (b > 0) {
    a %= b;
    swap a, b;
  }
  return a;
}

We can now find the equation of the line determined by the first two points in expected format:

if (by < ay) {
  A = ay - by;
  B = bx - ax;
} else {
  A = by - ay;
  B = ax - bx;
}
if (B < 0)
  signB = -1;
else 
  signB = 1;
temp = gcf(A, signB * B);
A /= temp;
B /= temp;
if (A == 0)
  B = 1;
C = -(A * ax + B * ay);

signB is used because the GCF function can only be used on positive integers. It is possible that the formula will determine A = 0 and B < 0, after dividing both by their GCF, we'll have B = -1. For purposes of the formatting, we'll set B = 1.

Also note that if we didn't use temp to store the GCF of A and B and instead immediately divided A by the GCF, we would no longer find the common factors with which B needs to be divided.

Then we determine if the other points are on this line with the use of flag:

flag = TRUE;
while (index = 3; index <= points; index ++) {
  input cx, cy;
  if (flag && (A * cx + B * cy + C != 0))
    flag = FALSE;
}

The other difficulty is in the output of the equation of the line when the points given are collinear. Several conditions are to be considered, as shown below:

  if (A > 1)
    output A;
  if (A > 0)
    output "x";
  if (B > 0)
    output "+";
  if (B == -1)
    output "-";
  if (B < -1 || B > 1)
    output B;
  if (B != 0)
    output "y";
  if (C > 0)
    output "+";
  if (C != 0)
    output C
  output "=0";