const char * UsageLines [] = {
	"Usage: llfind (latitude) (longitude)... < (input file)"
	"",
	"Finds points inside a perimeter containing straight line segments",
	"oriented E-W which are specified by latitude, and straight line",
	"segments oriented N-S which are specified by longitude.",
	"Input must contain lines beginning with:",
	"\t(latitude),(longitude)",
	"",
	"Outputs points that are inside (or on) the borders specified.",
	"Rounds input and borders to and displays output at 4 decimal places.",
	"Displays area in \"GeoAres\": a GeoAre is a rectangle whose",
	"sides are .0001 degree latitude, and .0001 degree longitude apart.",
	"(1 sq km = 8100 GeoAres at the equator,",
	" 1 sq km = 12600 GeoAres at 50 degrees latitude.)",
	"",
	"March 10, 2013",
	"Latest version can be found at:",
	" gopher -p users/julianbr sdf.org",
	"or: gopher://sdf.org/1/users/julianbr",
	};
const int NumUsageLines = sizeof (UsageLines)/sizeof (UsageLines [0] );

#include <stdlib.h>
#include <stdio.h>
#define NumDecimalPlaces 4


int ReadLocation (
		long int * northPtr,
		long int * eastPtr,
		int * endOfInputLinePtr,
		int * endOfInputPtr)
	{
	char sign;
	int decimalPosition, LatitudeAndLongitudeOk, c;

	LatitudeAndLongitudeOk = 0;
	endOfInputLinePtr [0] = 0;
	c = getchar ();
	sign = '+';
	if (c == '-' || c == '+') {
		sign = c;
		c = getchar ();
		}
	northPtr [0] = 0;
	while (c >= '0' && c <= '9') {
		northPtr [0] = 10*northPtr [0] + (c - '0');
		c = getchar ();
		}
	decimalPosition = 0;
	if (c == '.') {
		c = getchar ();
		while (c >= '0' && c <= '9') {
			if (decimalPosition == NumDecimalPlaces) {
				if (c > '4')
					northPtr [0]++;
				}
			else if (decimalPosition < NumDecimalPlaces)
				northPtr [0]
					= 10*northPtr [0] + (c - '0');
			decimalPosition++;
			c = getchar ();
			}
		}
	while (decimalPosition < NumDecimalPlaces) {
		northPtr [0] = 10*northPtr [0];
		decimalPosition++;
		}
	if (sign == '-')
		northPtr [0] = - northPtr [0];
	if (c == ',') {
		c = getchar ();
		sign = '+';
		if (c == '-' || c == '+') {
			sign = c;
			c = getchar ();
			}
		eastPtr [0] = 0;
		while (c >= '0' && c <= '9') {
			eastPtr [0] = 10*eastPtr [0] + (c - '0');
			c = getchar ();
			}
		decimalPosition = 0;
		if (c == '.') {
			c = getchar ();
			while (c >= '0' && c <= '9') {
				if (decimalPosition == NumDecimalPlaces) {
					if (c > '4')
						eastPtr [0]++;
					}
				else if (decimalPosition < NumDecimalPlaces)
					eastPtr [0]
						= 10*eastPtr [0]
						+ (c - '0');
				decimalPosition++;
				c = getchar ();
				}
			}
		while (decimalPosition < NumDecimalPlaces) {
			eastPtr [0] = 10*eastPtr [0];
			decimalPosition++;
			}
		if (sign == '-')
			eastPtr [0] = - eastPtr [0];
		LatitudeAndLongitudeOk = 1;
		}
	if (c != EOF && c != '\n' && c != ' ') {
		fprintf (stderr, "***llfind: Improper '%c'", c);
		LatitudeAndLongitudeOk = 0;
		}
	else if (c != EOF && !LatitudeAndLongitudeOk)
		fprintf (stderr, "***llfind: Comma not found");
	if (c == EOF) {
		endOfInputLinePtr [0] = 1;
		endOfInputPtr [0] = 1;
		}
	if (c == '\n')
		endOfInputLinePtr [0] = 1;
	return LatitudeAndLongitudeOk;
	}


long int ReadBoundary (char * Boundary)
	{
	long int boundaryValue;
	int decimalPosition;
	char sign, * ptr;

	ptr = Boundary;
	sign = '+';
	if (ptr [0] == '-' || ptr [0] == '+') {
		sign = ptr [0];
		ptr++;
		}
	boundaryValue = 0;
	while (ptr [0] >= '0' && ptr [0] <= '9') {
		boundaryValue = 10*boundaryValue + (ptr [0] - '0');
		ptr++;
		}
	decimalPosition = 0;
	if (ptr [0] == '.') {
		ptr++;
		while (ptr [0] >= '0' && ptr [0] <= '9') {
			if (decimalPosition == NumDecimalPlaces) {
				if (ptr [0] > '4')
					boundaryValue++;
				}
			else if (decimalPosition < NumDecimalPlaces)
				boundaryValue
					= 10*boundaryValue
					+ (ptr [0] - '0');
			decimalPosition++;
			ptr++;
			}
		}
	while (decimalPosition < NumDecimalPlaces) {
		boundaryValue = 10*boundaryValue;
		decimalPosition++;
		}
	if (sign == '-')
		boundaryValue = - boundaryValue;
	return boundaryValue;
	}


void FindAreaInsideBoundaries (
		int numBoundaries,
		char * * Boundaries)
	{
	long int cwArea, east;
	int i;

	cwArea = 0;
	east = 0;
	for (i = 1; i < numBoundaries; i += 2) {
		east += ReadBoundary (Boundaries [i] );
		}
	east /= numBoundaries/2;
	for (i = 1; i < numBoundaries; i += 2) {
		cwArea += (ReadBoundary (Boundaries [(i + 1)%numBoundaries] )
				- ReadBoundary (Boundaries [i - 1] ) )
			*(east - ReadBoundary (Boundaries [i] ) );
		}
	if (cwArea < 0)
		cwArea = - cwArea;
	fprintf (stderr, "llfind: %ld GeoAres", cwArea);
	fprintf (stderr, " inside specified boundaries.\n");
	}


int IsInsideOrOnBoundaries (
		long int north,
		long int east,
		int numBoundaries,
		char * * Boundaries)
	{
	long int north1, east2, north3, east4;
	int numCrossings, i;

	numCrossings = 0;
	for (i = 0; i < numBoundaries/2; i++) {
		north1 = ReadBoundary (
				Boundaries [(i + i + 0)%numBoundaries] );
		east2 = ReadBoundary (
				Boundaries [(i + i + 1)%numBoundaries] );
		north3 = ReadBoundary (
				Boundaries [(i + i + 2)%numBoundaries] );
		east4 = ReadBoundary (
				Boundaries [(i + i + 3)%numBoundaries] );
		if (east == east2
				&& !(north < north1 && north < north3)
				&& !(north > north1 && north > north3) )
			return 1;
		else if (north == north3
				&& !(east < east2 && east < east4)
				&& !(east > east2 && east > east4) )
			return 1;
		else if (north >= north1 && north < north3) {
			if (east >= east2)
				numCrossings++;
			}
		else if (north >= north3 && north < north1) {
			if (east >= east2)
				numCrossings--;
			}
		}
	if (numCrossings == 0)
		return 0;
	return 1;
	}


int BoundaryOk (char * Boundary)
	{
	char * ptr;

	ptr = Boundary;
	if (ptr [0] == '-' || ptr [0] == '+')
		ptr++;
	while (ptr [0] >= '0' && ptr [0] <= '9')
		ptr++;
	if (ptr [0] == '.')
		ptr++;
	while (ptr [0] >= '0' && ptr [0] <= '9')
		ptr++;
	if (ptr [0] == '\0')
		return 1;
	return 0;
	}


int BoundariesOk (int numBoundaries, char * * Boundaries)
	{
	int i, ok;

	ok = 1;
	for (i = 0; i < numBoundaries; i++) {
		if (!BoundaryOk (Boundaries [i] ) ) {
			fprintf (stderr, "***llfind: Improper boundary:");
			fprintf (stderr, " \"%s\".\n", Boundaries [i] );
			ok = 0;
			}
		}
	return ok;
	}


void WriteLocation (
		long int north,
		long int east,
		int endOfInputLine,
		int * endOfInputPtr)
	{
	unsigned long int value, factor;
	int i, c;

	if (north < 0) {
		putchar ('-');
		value = - north;
		}
	else {
		putchar ('+');
		value = north;
		}
	factor = 1;
	for (i = 0; i < NumDecimalPlaces + 2; i++)
		factor *= 10;
	for (i = 0; i < 2; i++) {
		factor /= 10;
		putchar ('0' +  value/factor%10);
		}
	putchar ('.');
	for (i = 0; i < NumDecimalPlaces; i++) {
		factor /= 10;
		putchar ('0' + value/factor%10);
		}
	putchar (',');
	if (east < 0) {
		putchar ('-');
		value = - east;
		}
	else {
		putchar ('+');
		value = east;
		}
	factor = 1;
	for (i = 0; i < NumDecimalPlaces + 3; i++)
		factor *= 10;
	for (i = 0; i < 3; i++) {
		factor /= 10;
		putchar ('0' + value/factor%10);
		}
	putchar ('.');
	for (i = 0; i < NumDecimalPlaces; i++) {
		factor /= 10;
		putchar ('0' + value/factor%10);
		}
	if (!endOfInputLine) {
		putchar (' ');
		c = getchar ();
		while (c != EOF && c != '\n') {
			putchar (c);
			c = getchar ();
			}
		if (c == EOF)
			endOfInputPtr [0] = 1;
		}
	putchar ('\n');
	}


void FindLocationsOnOrInsideBoundaries (
		int numBoundaries,
		char * * Boundaries)
	{
	unsigned long int all, inside, lineNum;
	long int north, east;
	int endOfInputLine, endOfInput, ok, c;

	ok = 1;
	all = 0;
	inside = 0;
	lineNum = 0;
	endOfInput = 0;
	while (!endOfInput) {
		lineNum++;
		if (ReadLocation (
				& north,
				& east,
				& endOfInputLine,
				& endOfInput) ) {
			all++;
			if (IsInsideOrOnBoundaries (
					north,
					east,
					numBoundaries,
					Boundaries) ) {
				inside++;
				WriteLocation (
						north,
						east,
						endOfInputLine,
						& endOfInput);
				}
			else if (!endOfInputLine) {
				c = getchar ();
				while (c != EOF && c != '\n')
					c = getchar ();
				if (c == EOF)
					endOfInput = 1;
				}
			}
		else if (!endOfInput) {
			ok = 0;
			fprintf (stderr, " in line #%lu.\n", lineNum);
			if (!endOfInputLine) {
				c = getchar ();
				while (c != EOF && c != '\n')
					c = getchar ();
				if (c == EOF)
					endOfInput = 1;
				}
			}
		}
	if (ok) {
		fprintf (stderr, "llfind: Found %lu inside or", inside);
		fprintf (stderr, " on boundaries out of %lu total.\n", all);
		}
	}

int main (int argc, char * argv [] )
	{
	int i;

	if (argc < 2) {
		for (i = 0; i < NumUsageLines; i++)
			printf ("%s\n", UsageLines [i] );
		}
	else if ((argc - 1)%2 == 1)
		printf ("***llfind: must specify number pairs.\n");
	else if ((argc - 1) > 0 && BoundariesOk (argc - 1, argv + 1) ) {
		FindAreaInsideBoundaries (argc - 1, argv + 1);
		FindLocationsOnOrInsideBoundaries (argc - 1, argv + 1);
		}
	return 0;
	}