const char * UsageLines [] = {
	"Usage: polygontopbm (width) (height)",
	"Reads space-separated points, from standard input, in the form",
	"\tacross,down",
	"\twhere across and down are positive or negative integers.",
	"Writes, to standard output, a P4 PBM image.",
	"The polygon whose corners are listed on any input line are",
	"filled with '1' pixels on the output image.",
	"Elsewhere the output pixels are '0'.",
	"On each input line, everything after # is treated as a comment.",
	"The leftmost column of pixels is considered - (width)/2 across.",
	"The topmost row of pixels is considered - (height)/2 down.",
	"August 25, 2011.  Newest is at gopher -p users/julianbr sdf.org",
	};
const int NumUsageLines = sizeof (UsageLines)/sizeof (UsageLines [0] );


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

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


int IsInsidePolygons (
		int across,
		int down,
		struct Polygon * Polygons)
	{
	struct Polygon * Polygon;
	struct Corner * Corner;
	int across1, across2, down1, down2;
	int NumCrossings;
	int IsInsidePolygons;

	IsInsidePolygons = 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)
			IsInsidePolygons = 1;
		Polygon = Polygon->next;
		}
	return IsInsidePolygons;
	}


int ReadPolygons (struct Polygon * * PolygonsPtr)
	{
	struct Polygon * * PolygonPtr;
	struct Corner * Corner;
	unsigned int LineNum;
	int IsNegative, FoundAcross, across, FoundDown, down;
	int c, ok;

	ok = 1;
	LineNum = 0;
	PolygonsPtr [0] = NULL;
	PolygonPtr = PolygonsPtr;
	c = getchar ();
	while (c != EOF) {
		LineNum++;
		Corner = NULL;
		while (c != EOF && c != '\n') {
			while (c == ' ')
				c = getchar ();
			/* read across */
			IsNegative = 0;
			if (c == '+')
				c = getchar ();
			else if (c == '-') {
				IsNegative = 1;
				c = getchar ();
				}
			FoundAcross = 0;
			across = 0;
			while (c >= '0' && c <= '9') {
				FoundAcross = 1;
				across = 10*across + (c - '0');
				c = getchar ();
				}
			if (IsNegative)
				across = - across;
			if (c == ',')
				c = getchar ();
			else
				FoundAcross = 0;

			/* read down */
			IsNegative = 0;
			if (c == '+')
				c = getchar ();
			else if (c == '-') {
				IsNegative = 1;
				c = getchar ();
				}
			FoundDown = 0;
			down = 0;
			while (c >= '0' && c <= '9') {
				FoundDown = 1;
				down = 10*down + (c - '0');
				c = getchar ();
				}
			if (IsNegative)
				down = - down;

			if (c != EOF && c != '\n' && c != ' ' && c != '#') {
				fprintf (stderr, "***polygontopbm: Improper");
				fprintf (stderr, " '%c'", c);
				fprintf (stderr, " in line #%u.\n", LineNum);
				while (c != EOF && c != '\n' && c != ' '
							&& c != '#')
					c = getchar ();
				ok = 0;
				}
			else if (FoundAcross && !FoundDown) {
				fprintf (stderr, "***polygontopbm: Incomplete");
				
				fprintf (stderr, " across,down");
				fprintf (stderr, " in line #%u.\n", LineNum);
				ok = 0;
				}
			else if (FoundAcross && FoundDown) {
				if (Corner == NULL) {
					PolygonPtr [0] = malloc (sizeof (
							PolygonPtr [0] [0] ) );
					if (PolygonPtr [0] != NULL) {
						PolygonPtr [0]->next = NULL;
						Corner
							= malloc (sizeof (
							Corner [0] ) );
						PolygonPtr [0]->Corners
							= Corner;
						PolygonPtr = & PolygonPtr [0]
								->next;
						}
					}
				else {
					Corner->next = malloc (
							sizeof (Corner [0] ) );
					Corner = Corner->next;
					}
				if (Corner == NULL) {
					fprintf (stderr, "***polygontopbm:");
					fprintf (stderr, " Not enough");
					fprintf (stderr, " memory.\n");
					ok = 0;
					}
				else {
					Corner->across = across;
					Corner->down = down;
					Corner->next = NULL;
					}
				}
			if (c == '#') {
				while (c != EOF && c != '\n')
					c = getchar ();
				}
			}
		if (c != EOF)
			c = getchar ();
		}
	return ok;
	}


void WritePolygons (
		struct Polygon * Polygons,
		int width,
		int height)
	{
	/* int i, j, k, m, LineSize, OutputBuffer, pixel; */
	int across, down, OutputWeight, OutputValue;

	printf ("P4\n%d %d\n", width, height);
	for (down = - height/2; down < height - height/2; down++) {
		OutputWeight = 128;
		OutputValue = 0;
		for (across = - width/2; across < width - width/2; across++) {
			if (IsInsidePolygons (across, down, Polygons) )
				OutputValue += OutputWeight;
			OutputWeight /= 2;
			if (OutputWeight == 0) {
				putchar (OutputValue);
				OutputWeight = 128;
				OutputValue = 0;
				}
			}
		if (OutputWeight < 128)
			putchar (OutputValue);
		}
	}


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, i;
	char c;

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