The input section is simple: just grab 'n' and the x,y coordinates.
Because this problem depends on speed, first observe that the distance is, for sorting purposes, equivalent to sorting on the square of the distance (thus avoiding n*n/2 sqrt calls). Second, observe that the distance is symmetric, so we can calculate the distance matrix twice as fast as otherwise.
All that remains is 'playing cow tag'. An outer loop runs n-1 times, starting at the first cow (the cows are numbered 0..n-1 on the inside of this solution). A 'boolean' array named "dead" keeps track of which cows are not dead yet. The inner loop searches non-dead cows for the closest one.
The answer is printed as one more than the 0-offset cow id.
A linked list could speed the searching for distances and dead cows. Such an implementation is not currently expected of Bronze-level competitors.
Coach Rob's code:
#include <stdio.h> #define MAXN 951 int dist[MAXN][MAXN]; int x[MAXN], y[MAXN], curcow; int dead[MAXN]; int n; main () { FILE *fin = fopen ("cowtag.in", "r"); FILE *fout = fopen ("cowtag.out", "w"); int i, j, bestdist, bestcow; fscanf(fin, "%d", &n); for (i = 0; i < n; i++) fscanf (fin, "%d %d", &x[i], &y[i]); for (i = 0; i < n; i++) { for (j=i+1; j < n; j++) { int a = x[i]-x[j], b = y[i]-y[j]; dist[j][i] = dist[i][j] = a*a+b*b; } } curcow = 0; for (i = 0; i < n-1; i++) { /* tag nearest cow */ bestdist = 2000000000; for (j = 0; j < n; j++) { if (dead[j] || curcow == j) continue; if (dist[curcow][j] < bestdist) { bestdist = dist[curcow][j]; bestcow = j; } } dead[bestcow] = 1; do { if (++curcow >= n) curcow = 0; } while (dead[curcow]); } fprintf (fout, "%d\n", curcow+1); exit (0); }