//#define _GNU_SOURCE

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


struct point {
	int x;
	int y;
};


struct point *
point_copy(struct point const * other)
{
	struct point * p = malloc(sizeof(struct point));
	if (!p)
		return NULL;
	p->x = other->x;
	p->y = other->y;
	return p;
}


int
point_cmp(struct point const * a, struct point const * b)
{
	return a->x - b->x != 0
		? a->x - b->x
		: a->y - b->y;
}


int
point_tcmp(void const * a, void const * b)
{
	return point_cmp(a, b);
}


int
main()
{
	char buf[BUFSIZ];
	struct point head = {0}, * tail = point_copy(&head);
	void * tails = NULL;
	int ntails = 0;

	tsearch(tail, &tails, point_tcmp);
	tail = point_copy(tail);
	++ntails;
	fprintf(stderr, "Tail visiting %d,%d\n", tail->x, tail->y);

	while (fgets(buf, sizeof(buf), stdin)) {
		int dist, dx, dy;

		if (!isalpha(buf[0])
				|| buf[1] != ' '
				|| !isdigit(buf[2]))
		{
			fprintf(stderr, "Unexpected input: %s\n", buf);
			return -1;
		}

		dist = atoi(buf + 2);
		if (dist == 0) {
			fprintf(stderr, "Unexpected distance in: %s\n", buf);
			// Allow 0 for now...
		}
		switch (buf[0]) {
		case 'L': head.x -= dist; break;
		case 'R': head.x += dist; break;
		case 'U': head.y += dist; break;
		case 'D': head.y -= dist; break;
		default:
			  fprintf(stderr, "Unexpected input: %s\n", buf);
			  return -1;
		}
		fprintf(stderr, "Head %c %d to %d,%d\n", buf[0], dist, head.x, head.y);

		dx = head.x - tail->x;
		dy = head.y - tail->y;
		while (dx * dx + dy * dy > 2) {
			struct point ** pp;

			if (dx > 0) {
				++tail->x;
				--dx;
			}
			if (dx < 0) {
				--tail->x;
				++dx;
			}
			if (dy > 0) {
				++tail->y;
				--dy;
			}
			if (dy < 0) {
				--tail->y;
				++dy;
			}
			fprintf(stderr, " Tail visiting %d,%d", tail->x, tail->y);

			// Search/insert current tail in visited tails
			pp = tsearch(tail, &tails, point_tcmp);
			if (*pp == tail) {
				// This was a new one, tail is now in the tree
				//fprintf(stderr, " (new)");
				tail = point_copy(tail);
				++ntails;
			}
			else {
				fprintf(stderr, " (old)");
			}

			fprintf(stderr, "\n");
		}
	}

	printf("Unique tail spots visited: %d\n", ntails);

	free(tail);
#ifdef _GNU_SOURCE
	tdestroy(tails, free);
#endif

	return 0;
}