char * UsageLines [] = {
	"Usage: p4paths (width) (height) (thickness)",
	"Produces PBM image of specified dimensions, with '1' pixels",
	"inside path formed by joining specified corners with",
	"straight line segments of specified thickness (in pixels).",
	"Reads across and down, one set per line, from standard input.",
	"0 0  corresponds to the upper left corner of the image.",
	"Paths are separated by a blank line.",
	"Writes to standard output.",
	"January 25, 2023.  Newest is at gopher -p users/julianbr sdf.org",
	};
int NumUsageLines = sizeof (UsageLines) / sizeof (UsageLines [0] );


struct Corner {
	int across;
	int down;
	struct Corner * next;
	};


struct Path {
	struct Corner * corners;
	struct Path * next;
	};


#include <stdio.h>
#include <stdlib.h>


struct Path * ReadPaths (void)
	{
	struct Path * paths;
	struct Path * * pathPtr;
	struct Corner * * cornerPtr;
	int lineCount;
	int foundAcross, foundDown, acrossNegative, downNegative;
	int across, down;
	int memoryOk;
	int c;

	paths = NULL;
	pathPtr = & paths;
	memoryOk = 1;
	lineCount = 0;
	c = getchar ();
	while (c == ' ')
		c = getchar ();
	while (c != EOF) {
		lineCount++;
		across = 0;
		foundAcross = 0;
		acrossNegative = 0;
		down = 0;
		foundDown = 0;
		downNegative = 0;
		if (c == '-') {
			acrossNegative = 1;
			c = getchar ();
			}
		while (c >= '0' && c <= '9') {
			across = 10*across + (c - '0');
			foundAcross = 1;
			c = getchar ();
			}
		if (acrossNegative)
			across = - across;
		while (c == ' ')
			c = getchar ();
		if (c == '-') {
			downNegative = 1;
			c = getchar ();
			}
		while (c >= '0' && c <= '9') {
			down = 10*down + (c - '0');
			foundDown = 1;
			c = getchar ();
			}
		if (downNegative)
			down = - down;
		while (c == ' ')
			c = getchar ();
		if (c != '\n' && c != EOF) {
			fprintf (stderr, "***p4paths: Improper");
			fprintf (stderr, " '%c' in line %d.\n", c, lineCount);
			while (c != '\n' && c != EOF)
				c = getchar ();
			}
		else if ((acrossNegative && !foundAcross)
				|| (downNegative && !foundDown) ) {
			fprintf (stderr, "***p4paths: Improper");
			fprintf (stderr, " '-' in line %d.\n", lineCount);
			}
		else if (foundAcross && !foundDown) {
			fprintf (stderr, "***p4paths: Found");
			fprintf (stderr, " across but not down in");
			fprintf (stderr, " line %d.\n", lineCount);
			}
		if (c == '\n')
			c = getchar ();
		if (foundAcross && foundDown) {
			if (memoryOk && pathPtr [0] == NULL) {
				pathPtr [0] = malloc (sizeof (pathPtr [0] [0] ) );
				if (pathPtr [0] == NULL)
					memoryOk = 0;
				else {
					pathPtr [0]->next = NULL;
					cornerPtr = & pathPtr [0]->corners;
					}
				}
			if (memoryOk) {
				cornerPtr [0] = malloc (sizeof (cornerPtr [0] [0] ) );
				if (cornerPtr [0] == NULL)
					memoryOk = 0;
				}
			if (memoryOk) {
				cornerPtr [0]->across = across;
				cornerPtr [0]->down = down;
				cornerPtr [0]->next = NULL;
				cornerPtr = & cornerPtr [0]->next;
				}
			}
		else if (pathPtr [0] != NULL)
			pathPtr = & pathPtr [0]->next;
		}
	if (!memoryOk)
		fprintf (stderr, "***p4paths: Not enough memory.\n");
	return paths;
	}


void ShowPaths (struct Path * paths)
	{
	struct Path * path;
	struct Corner * corner;

	path = paths;
	while (path != NULL) {
		corner = path->corners;
		while (corner != NULL) {
			printf ("%d %d  ", corner->across, corner->down);
			corner = corner->next;
			}
		printf ("\n");
		path = path->next;
		}
	}


void WritePaths (struct Path * paths, int width, int height, int pathwidth)
	{
	struct Path * path;
	struct Corner * corner;
	int across1, across2, down1, down2;
	int pathheight, segmentwidth, segmentheight;
	int along, along1, along2, below, below1, below2;
	int isOnPath;
	int across, down, weight;
	unsigned char value;

	printf ("P4\n%d %d\n", width, height);
	for (down = 0; down < height; down++) {
		value = 0;
		weight = 128;
		for (across = 0; across < width; across++) {
			isOnPath = 0;
			path = paths;
			while (path != NULL) {
				corner = path->corners;
				while (corner != NULL) {
					across1 = corner->across;
					down1 = corner->down;
					if (4*((across - across1)*(across - across1)
						+ (down - down1)*(down - down1) )
							< pathwidth*pathwidth)
						isOnPath = 1;
					corner = corner->next;
					}
				corner = path->corners;
				while (corner != NULL && corner->next != NULL) {
					across1 = corner->across;
					down1 = corner->down;
					across2 = corner->next->across;
					down2 = corner->next->down;
					segmentwidth = across2 - across1;
					if (segmentwidth < 0)
						segmentwidth = - segmentwidth;
					segmentheight = down2 - down1;
					if (segmentheight < 0)
						segmentheight = - segmentheight;
					if (segmentwidth == 0 && segmentheight == 0)
						pathheight = 0;
					else if (segmentwidth > segmentheight)
						pathheight = pathwidth*segmentwidth
							+ pathwidth*segmentheight
							*segmentheight/(2*segmentwidth);
					else
						pathheight = pathwidth*segmentheight
							+ pathwidth*segmentwidth
							*segmentwidth/(2*segmentheight);
					along1 = (across2 - across1)*across1
						+ (down2 - down1)*down1;
					below1 = across2*down1 - across1*down2;
					along2 = (across2 - across1)*across2
						+ (down2 - down1)*down2;
					along = (across2 - across1)*across
						+ (down2 - down1)*down;
					below = - (down2 - down1)*across
						+ (across2 - across1)*down;
					if (along > along1 && along < along2) {
						below2 = below1 - pathheight/2;
						if (below > below2
						&& below < below2 + pathheight)
							isOnPath = 1;
						}
					corner = corner->next;
					}
				path = path->next;
				}
			if (isOnPath)
				value += weight;
			weight /= 2;
			if (weight == 0) {
				putchar (value);
				weight = 128;
				value = 0;
				}
			}
		if (weight < 128)
			putchar (value);
		}
	}


void ClosePaths (struct Path * paths)
	{
	struct Path * path, * nextPath;
	struct Corner * corner, * nextCorner;

	path = paths;
	while (path != NULL) {
		nextPath = path->next;
		corner = path->corners;
		while (corner != NULL) {
			nextCorner = corner->next;
			free (corner);
			corner = nextCorner;
			}
		free (path);
		path = nextPath;
		}
	}


int main (int argc, char * * argv)
	{
	struct Path * paths;
	int width, height, thickness;
	int i;
	char c;

	if (argc == 1) {
		for (i = 0; i < NumUsageLines; i++)
			printf ("%s\n", UsageLines [i] );
		}
	else if (argc != 4
			|| sscanf (argv [1], "%d%c", & width, & c) != 1
			|| sscanf (argv [2], "%d%c", & height, & c) != 1
			|| sscanf (argv [3], "%d%c", & thickness, & c) != 1)		
		fprintf (stderr, "Usage %s (width) (height) (thickness)\n", argv [0] );
	else {
		paths = ReadPaths ();
		WritePaths (paths, width, height, thickness);
		ClosePaths (paths);
		}
	return 0;
	}