USACO OCT06 2006 Problem 'moat' Analysis

by Rob Kolstad

The task is to find the shortest fence the completely surrounds a series of points. This task is generically known as 'Convex Hull' and, in various incarnations, is widely studied. Changing the requirements just a bit (collinear points, larger N) leads to tremendous challenges.

As posed, it is not so difficult for a programmer to invent the 'gift-wrapping' algorithm, which starts at some point known to be among the answer set (e.g., the leftmost, topmost point) and successively find points which maximize the 'angle' between the current point and the next point. Other algorithms are possible, of course.

My solution uses the signs of dx and dy to aid in finding the proper 'maximum' slope. Other solutions use very clever enhancements to atan2 to find angles. It sadly has special cases for vertical lines where the slope is infinite. The atan2 solutions do not have this special case in their code; it is in the atan2 routine :) .

#include <stdio.h>
#include <math.h>

FILE *fin, *fout;
int npoints, x[5000], y[5000], curx, cury;
double dist;

#define SQ(x) ( (x) * (double)(x) )

adddist(i) {
    dist += sqrt(SQ(x[i]-curx) + (double)SQ(y[i]-cury));
}

/*
    Search for the point with highest slope through curx,cury.
    Search is constrained by certain dx,dy restrctions
*/
search(stage) {
    int i, bestindex = -1, ok;
    double slope, bestslope = -999999;
    int listindex = 0;
    for (i = 0; i < npoints; i++) {
	switch (stage) {
	    case 1: ok = x[i]-curx > 0 && y[i]-cury >= 0; break;
	    case 2: ok = x[i]-curx > 0 && y[i]-cury <= 0; break;
	    case 3: ok = x[i]-curx < 0 && y[i]-cury <= 0; break;
	    case 4: ok = x[i]-curx < 0 && y[i]-cury > 0;  break;
	}
	if (!ok) continue;

        slope = (y[i]-cury) / (double)(x[i]-curx);
        if (slope > bestslope) {
	    bestindex = i;
	    bestslope = slope;
        }
    }
    if (bestindex == -1) return 0; 
    adddist (bestindex);
    curx = x[bestindex]; cury = y[bestindex];
    return 1;
}

int findvert() {
    int i;
    for (i = 0; i < npoints; i++) {
        if (x[i] != curx || y[i] == cury) continue;
	adddist(i);
        curx = x[i]; cury = y[i];
	return;
    }
}

main () {
    int i, bestindex;
    fin = fopen ("moat.in", "r");
    fout = fopen ("moat.out", "w");
    fscanf (fin, "%d", &npoints);
    for (i = 0; i < npoints; i++) 
	fscanf (fin, "%d %d", &x[i], &y[i]);

    /* find leftmost, highest point */
    bestindex = 0;		/* maybe it's point 0! */
    for (i = 0+1; i < npoints; i++) {
        if (x[i] < x[bestindex]) bestindex = i; 
        if (x[i] == x[bestindex] && y[i] > y[bestindex]) bestindex = i; 
    }
    curx = x[bestindex]; cury = y[bestindex];

/* find point with largest slope as long as dx>0 && dy >= 0 */
    while (search(1));
/* find point with biggest slope as long as dx>0 && dy < 0 */
    while (search(2));
/* find vertical line if it exists */
    findvert();
/* find point with biggest slope as long as dx<=0 && dy <= 0 */
    while (search(3));
/* find point with biggest slope as long as dx<0 && dy > 0 */
    while (search(4));
/* find vertical line if it exists */
    findvert();
    fprintf (stderr, "Total dist is %.2lf\n", dist);
    fprintf (fout, "%.2lf\n", dist);
    exit (0);
}