USACO NOV09 Problem 'claust' Analysis

by Rob Kolstad

This is another 'complete search' task. We must check all possible pairs (actually, only half of them -- the distance function is symmetric) to see which is closest. A double-nested loop suffices!

Here is my solution:

#include <stdio.h>

int x[2000], y[2000];
int n;

#define SQ(x) (((long long)x)*((long long)x))

main () {
    int i, j;
    long long shortest, t;
    int s1, s2;
    FILE *fin = fopen ("claust.in", "r");
    FILE *fout = fopen ("claust.out", "w");
    fscanf (fin, "%d", &n);
    for (i = 0; i < n; i++)
        fscanf (fin, "%d %d", &x[i], &y[i]);

    shortest = 1LL << 60;
    for (i = 0; i < n; i++)
        for (j = i+1; j < n; j++) {
            t = SQ(x[i]-x[j]) + (long long) SQ(y[i]-y[j]);
            if (t < shortest) {
                s1 = i+1;
                s2 = j+1;
                shortest = t;
            }
        }
    fprintf (fout, "%d %d\n", s1, s2);
    exit (0);
}