Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

Orchard Trees

143.c

/* 143 - Orchard Trees */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIGN(a) ((a==0) ? 0 : (a>0) ? 1 : -1)

#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MAX(a,b) ((a) > (b) ? (a) : (b))

typedef struct {
	int x;
	int y;
} punto;

typedef struct {
	punto p1;
	punto p2;
	punto p3;
} triangle;

int
cross(punto p1, punto p2) {
	return p1.x*p2.y - p1.y*p2.x;
}

punto
psub(punto p1, punto p2) {
	punto p;
	p.x = p2.x - p1.x;
	p.y = p2.y - p1.y;
	return p;
}

int
inside(punto p, triangle t) {
	int sign = 0;
	int s;

	s = SIGN(cross(psub(t.p1, t.p2), psub(t.p1, p)));
	if (!sign) sign=s;
	if (s && s!=sign) {
		return 0;
	}
	s = SIGN(cross(psub(t.p2, t.p3), psub(t.p2, p)));
	if (!sign) sign=s;
	if (s && s!=sign) {
		return 0;
	}
	s = SIGN(cross(psub(t.p3, t.p1), psub(t.p3, p)));
	if (!sign) sign=s;
	if (s && s!=sign) {
		return 0;
	}
	return 1;
}

int
getvalue(void) {
	char str[1024];
	int d;
	char *s;

	if (scanf(" %s", str) != 1) {
		abort();
	}
	if (strspn(str, "0123456789.") != strlen(str) || strlen(str) > 6) {
		abort();
	}
	s = strchr(str, '.');
	d = 100 * atoi(str);
	if (!s) {
		return d;
	}
	strcat(str, "00");
	s[3] = 0;
	d += atoi(s+1);
	return d;
}

#define scale 100

int
main(void) {

	while (1) {
		triangle t;
		int i,j;
		int num=0;
		int mini,minj,maxi,maxj;

		t.p1.x = getvalue();
		t.p1.y = getvalue();
		t.p2.x = getvalue();
		t.p2.y = getvalue();
		t.p3.x = getvalue();
		t.p3.y = getvalue();

		if (t.p1.x==0 && t.p1.y==0 && t.p2.x==0 && t.p2.y==0 && t.p3.x==0 && t.p3.y==0) {
			return 0;
		}

#if 1
		mini = MIN(t.p1.x, t.p2.x);
		mini = MIN(mini, t.p3.x);
		mini = MAX(mini, scale);
		mini += scale-1;
		mini /= scale; mini *= scale;
		minj = MIN(t.p1.y, t.p2.y);
		minj = MIN(minj, t.p3.y);
		minj = MAX(minj, scale);
		minj += scale-1;
		minj /= scale; minj *= scale;
		maxi = MAX(t.p1.x, t.p2.x);
		maxi = MAX(maxi, t.p3.x);
		maxi = MIN(maxi, 99*scale);
		maxi /= scale; maxi *= scale;
		maxj = MAX(t.p1.y, t.p2.y);
		maxj = MAX(maxj, t.p3.y);
		maxj = MIN(maxj, 99*scale);
		maxj /= scale; maxj *= scale;
#if 0
		printf("mini=%d, maxi=%d, minj=%d, maxj=%d\n", mini, maxi, minj, maxj);
#endif
#endif

#if 0
		printf("t.p1: (%d,%d)\n", t.p1.x, t.p1.y);
		printf("t.p2: (%d,%d)\n", t.p2.x, t.p2.y);
		printf("t.p3: (%d,%d)\n", t.p3.x, t.p3.y);
		printf("\n");
		continue;
#endif

		for (i=mini; i<=maxi; i+=scale) {
			for (j=minj; j<=maxj; j+=scale) {
				punto p;
				p.x = i;
				p.y = j;
				if (inside(p, t)) {
					num++;
				}
			}
		}
		printf("%4d\n", num);
	}
	return 0;
}