The problem is "find sets of three collinear points from an input set" and furthermore to print them in a certain order. Regrettably, one must count the solutions before outputting them. Thus, either one must traverse the data twice or one must save the solutions and then output them (presumably, this is twice as fast as doing the problem twice).
Collinearity is probably most easily determined by determining whether the slope from some point 1 to some point 2 is the same as the slope from that same point 1 to some other point 3. One might be tempted to write code that compares slopes like this:
double slope1 = (y[j]-y[i])/(x[j]-x[i]);
double slope2 = (y[k]-y[i])/(x[k]-x[i]);
if (slope1 == slope2) {
/* solution found */
}
but this has the dual downsides of using slower floating point
arithmetic (slower than integers, anyway) and -- most dangerously
-- performing a floating point compare. It is axiomatic that
floating point compares suffer from failure due to slight inaccuracies
of floating point representation. Thus, one needs to cross-multiply:
if ( (y[j]-y[i]) * (x[k]-x[i]) == (y[k]-y[i]) * (x[j]-x[i]) ) {
/* solution found */
}
This calculation takes place entirely in integer arithmetic, with
the only downside of potential overflow if the values work out
poorly.
What's left? The triple nested loop so see the solutions.
Here is Rob's solution, written to work the first time with as much speed as one can muster for a first-try effort (which explains all the temporary variable assignments):
#include <stdio.h>
#include <math.h>
int coors[2000][2]; /* x,y */
int ans[2000][3]; /* cow ids */
int ncollinear;
idcompare(i,j) {
int k;
for (k = 0; k < 3; k++) {
if (ans[i][k] < ans[j][k]) return -1;
if (ans[i][k] > ans[j][k]) return 1;
}
return 0;
}
main () {
int i, j, k, n, t;
int x1,y1, x2,y2, x3,y3, dx1,dy1, dx2,dy2;
FILE *fin = fopen ("align.in", "r");
FILE *fout = fopen ("align.out", "w");
fscanf(fin, "%d", &n);
for (i = 0; i < n; i++)
fscanf(fin, "%d %d", &coors[i][0], &coors[i][1]);
for (i = 0; i < n; i++) {
x1 = coors[i][0];
y1 = coors[i][1];
for (j = i+1; j < n; j++) {
x2 = coors[j][0];
y2 = coors[j][1];
dx1 = x2 - x1;
dy1 = y2 - y1;
for (k = j+1; k < n; k++) {
x3 = coors[k][0];
y3 = coors[k][1];
dx2 = x3 - x2;
dy2 = y3 - y2;
if (dy1 * dx2 == dy2 * dx1) {
ans[ncollinear][0] = i+1; /* i,j,k already sorted */
ans[ncollinear][1] = j+1;
ans[ncollinear][2] = k+1;
ncollinear++;
}
}
}
}
fprintf(fout, "%d\n", ncollinear);
for (i = 0; i < ncollinear; i++)
fprintf (fout, "%d %d %d\n", ans[i][0], ans[i][1], ans[i][2]);
exit (0);
}