Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

Bumpy Objects

132.c

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

#define EPS 1E-10

#define eq(a,b) (fabs(a-b) < EPS)

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

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

typedef struct {
	char * name;
	double gx;
	double gy;
	int np;
	punto * p;
} poly;

punto
psub(punto p1, punto p2) {
	punto p;

	p.x = p2.x - p1.x;
	p.y = p2.y - p1.y;
	return p;
}

double
cross(punto v1, punto v2) {
	return v1.x*v2.y - v2.x*v1.y;
}

int
try(poly *p, int a, int b) {
	int i;
	int sign=0;
	double c;
	int max = MAX(a,b)+1;
	for (i=0; i<p->np; i++) {
		if (i==a || i==b) {
			continue;
		}
		c = cross(psub(p->p[a], p->p[b]), psub(p->p[a], p->p[i]));
		if (eq(c,0.0)) {
			max = MAX(max,i+1);
		} else if (sign==0) {
			sign = (int)(c / abs(c));
		} else {
			if (sign != (int)(c / abs(c))) {
#if DEBUG
				printf("HCK: try(%d,%d) = -1\n", a, b);
#endif
				return -1;
			}
		}
	}
#if DEBUG
				printf("HCK: try(%d,%d) = %d\n", a, b, max);
#endif
	return max;
}

void
doit(poly * p) {
	int i,j,k;
	int base=1000000000;
	for (i=0; i<p->np-1; i++) {
		for (j=i+1; j<p->np; j++) {
			k = try(p, i,j);
			if (k>0 && k<base) {
				base=k;
			}
		}
	}
	printf("%-20s%d\n", p->name, base);
}

int
main(void) {
	char buf[1024];
	poly p;
	double a,b;

	while (1) {
		fgets(buf, sizeof(buf), stdin);
		if (buf[0]=='#' && (buf[1]==' ' || buf[1]=='\r' || buf[1]=='\n' || buf[1]=='\0')) {
			return 0;
		}
		while (buf[strlen(buf)-1]=='\r' || buf[strlen(buf)-1]=='\n') {
			buf[strlen(buf)-1]='\0';
		}
		p.name = buf;
		scanf("%lf %lf", &p.gx, &p.gy);
		p.np = 0;
		while (scanf("%lf %lf", &a, &b)==2 && (!eq(a,0.0) || !eq(b,0.0))) {
			p.p = realloc(p.p, (p.np+1)*sizeof(punto));
			p.p[p.np].x = a;
			p.p[p.np].y = b;
			p.np++;
		}
		doit(&p);
		fgets(buf, 1024, stdin);
	}
}