char * UsageLines [] = {
	"Usage: p4polygons (width) (height)",
	"Produces PBM image of specified dimensions, with '1' pixels",
	"inside closed path formed by joining specified corners with",
	"straight line segments.",
	"Reads across and down, one set per line, from standard input.",
	"0 0  corresponds to the upper left corner of the image.",
	"Polygons 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 Polygon {
	struct Corner * corners;
	struct Polygon * next;
	};


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


struct Polygon * ReadPolygons (void)
	{
	struct Polygon * polygons;
	struct Polygon * * polygonPtr;
	struct Corner * * cornerPtr;
	int lineCount;
	int foundAcross, foundDown, acrossNegative, downNegative;
	int across, down;
	int memoryOk;
	int c;

	polygons = NULL;
	polygonPtr = & polygons;
	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, "***p4polygons: 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, "***p4polygons: Improper");
			fprintf (stderr, " '-' in line %d.\n", lineCount);
			}
		else if (foundAcross && !foundDown) {
			fprintf (stderr, "***p4polygons: Found");
			fprintf (stderr, " across but not down in");
			fprintf (stderr, " line %d.\n", lineCount);
			}
		if (c == '\n')
			c = getchar ();
		if (foundAcross && foundDown) {
			if (memoryOk && polygonPtr [0] == NULL) {
				polygonPtr [0] = malloc (sizeof (polygonPtr [0] [0] ) );
				if (polygonPtr [0] == NULL)
					memoryOk = 0;
				else {
					polygonPtr [0]->next = NULL;
					cornerPtr = & polygonPtr [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 (polygonPtr [0] != NULL)
			polygonPtr = & polygonPtr [0]->next;
		}
	if (!memoryOk)
		fprintf (stderr, "***p4polygons: Not enough memory.\n");
	return polygons;
	}


void ShowPolygons (struct Polygon * polygons)
	{
	struct Polygon * polygon;
	struct Corner * corner;

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


void WritePolygons (struct Polygon * polygons, int width, int height)
	{
	struct Polygon * polygon;
	struct Corner * corner;
	int across1, across2, down1, down2;
	int numCrossings, isDark;
	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++) {
			isDark = 0;
			polygon = polygons;
			while (polygon != NULL) {
				numCrossings = 0;
				corner = polygon->corners;
				while (corner != NULL) {
					across1 = corner->across;
					down1 = corner->down;
					if (corner->next == NULL) {
						across2 = polygon->corners->across;
						down2 = polygon->corners->down;
						}
					else {
						across2 = corner->next->across;
						down2 = corner->next->down;
						}
					if (down1 <= down && down < down2) {
						if (
							(across - across1)*(down2 - down1)
							>=
							(across2 - across1)*(down - down1)
							)
							numCrossings--;
						}
					else if (down1 > down && down >= down2) {
						if (
							(across - across2)*(down1 - down2)
							>=
							(across1 - across2)*(down - down2)
							)
							numCrossings++;
						}
					corner = corner->next;
					}
				if (numCrossings != 0)
					isDark = 1;
				polygon = polygon->next;
				}
			if (isDark)
				value += weight;
			weight /= 2;
			if (weight == 0) {
				putchar (value);
				weight = 128;
				value = 0;
				}
			}
		if (weight < 128)
			putchar (value);
		}
	}


void ClosePolygons (struct Polygon * polygons)
	{
	struct Polygon * polygon, * nextPolygon;
	struct Corner * corner, * nextCorner;

	polygon = polygons;
	while (polygon != NULL) {
		nextPolygon = polygon->next;
		corner = polygon->corners;
		while (corner != NULL) {
			nextCorner = corner->next;
			free (corner);
			corner = nextCorner;
			}
		free (polygon);
		polygon = nextPolygon;
		}
	}


int main (int argc, char * * argv)
	{
	struct Polygon * polygons;
	int width, height;
	int i;
	char c;

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