Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

Center of Masses

10002.c

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

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

typedef struct {
	punto p1;
	punto p2;
} segmento;

typedef struct {
	punto p;
	double mass;
} gravity;

int n;
punto pu[120];
gravity ga[120];

static int
minang(int o, int nl, punto *li) {
	int i,m=!o;
	for (i=0; i<nl; i++) {
		if (i==o) continue;
		if ((li[i].x-li[o].x)*(li[m].y-li[o].y)
			> (li[i].y-li[o].y)*(li[m].x-li[o].x)) {
			m=i;
		}
	}
	return m;
}

int
convex_hull(int N, punto * li) {
	int i,m=0;
	punto p;
	for (i=1; i<N; i++) {
		double c = li[i].y - li[m].y;
		if (c<0) m=i;
		if (!c && (li[i].x < li[m].x)) m=i;
	}
	p=li[0]; li[0]=li[m]; li[m]=p;
	i=0; m=1;
	while (1) {
		i = minang(m-1, N, li);
		if (i==0) return m;
		p=li[m]; li[m]=li[i]; li[i]=p;
		m++;
	}
}

double
modulo(punto p) {
	return sqrt(p.x*p.x + p.y*p.y);
}
punto
psub(punto p1, punto p2) {
	punto p;
	p.x = p1.x - p2.x;
	p.y = p1.y - p2.y;
	return p;
}
#define dist(a,b) modulo(psub(a,b))

double
coordy(segmento s, double x, int *ok) {
	if (s.p2.x == s.p1.x) {
		*ok = 0;
		return 0.0;
	}
	*ok = 1;
	return s.p1.y + (x-s.p1.x)*(s.p2.y-s.p1.y)/(s.p2.x-s.p1.x);
}

punto
corte(segmento s1, segmento s2, int *ok) {
	punto p;
	double A,B;
	*ok = 1;
	if (s1.p1.x == s1.p2.x) {
		p.x = s1.p1.x;
		p.y = coordy(s2, p.x, ok);
		return p;
	}
	if (s2.p1.x == s2.p2.x) {
		p.x = s2.p1.x;
		p.y = coordy(s1, p.x, ok);
		return p;
	}
	A = (s1.p2.y - s1.p1.y) / (s1.p2.x - s1.p1.x);
	B = (s2.p2.y - s2.p1.y) / (s2.p2.x - s2.p1.x);
	if (A==B) {
		*ok=0;
		return p;
	}
	p.x = (s2.p1.y - s1.p1.y + A*s1.p1.x - B*s2.p1.x) / (A-B);
	p.y = s1.p1.y + A*(p.x-s1.p1.x);
	return p;
}

gravity
grav_tri(punto p1, punto p2, punto p3) {
	gravity g;
	segmento s1, s2;
	int ok;
	double s = (dist(p1,p2) + dist(p2,p3) + dist(p1,p3))/2.0;

	s1.p1 = p1;
	s1.p2.x = (p2.x+p3.x)/2.0;
	s1.p2.y = (p2.y+p3.y)/2.0;

	s2.p1 = p2;
	s2.p2.x = (p1.x+p3.x)/2.0;
	s2.p2.y = (p1.y+p3.y)/2.0;

	g.p = corte(s1, s2, &ok);
	if (!ok) abort();
	g.mass = sqrt(s*(s-dist(p1,p2))*(s-dist(p2,p3))*(s-dist(p1,p3)));
	return g;
}

gravity
add_grav(gravity g1, gravity g2) {
	gravity g;
	g.mass = g1.mass + g2.mass;
	g.p.x = (g1.mass*g1.p.x + g2.mass*g2.p.x) / g.mass;
	g.p.y = (g1.mass*g1.p.y + g2.mass*g2.p.y) / g.mass;
	return g;
}

int
main(void) {
	int i;

	while (1) {
		scanf("%d", &n);
		if (n<3) {
			break;
		}
		for (i=0; i<n; i++) {
			scanf("%lf %lf", &pu[i].x, &pu[i].y);
		}

#if 0
		if (convex_hull(n, pu) != n) abort();
#endif
		n = convex_hull(n, pu);

		for (i=1; i<n-1; i++) {
			ga[i-1] = grav_tri(pu[0], pu[i], pu[i+1]);
		}
		for (i=1; i<n-2; i++) {
			ga[0] = add_grav(ga[0], ga[i]);
		}
		printf("%.3f %.3f\n", ga[0].p.x, ga[0].p.y);
	}
	return 0;
}