Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

SCUD Busters

109.c

/* SCUD Busters */
#include <stdio.h>
#include <stdlib.h>

#define DEBUG 0

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

struct kingdom {
	int light;
	int num_sites;
	int num_vertices;
	punto sites[101];
};

struct kingdom k[20];

int
minang(int o, int N, punto * p) {
	int i,m=!o;

	for (i=o+1 ; i<N ; i++) {
		int ix,iy,mx,my;
		ix = p[i].x-p[o].x;
		iy = p[i].y-p[o].y;
		mx = p[m].x-p[o].x;
		my = p[m].y-p[o].y;
		if (ix*my > iy*mx) {
			m=i;
		} else if (ix*my == iy*mx) {
			if ((ix*ix + iy*iy) > (mx*mx + my*my)) {
				m=i;
			}
		}
	}
	return m;
}

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

	while (1) {
		i = minang(m-1,N,p);
		if (i==0) return m;
		q=p[m]; p[m]=p[i]; p[i]=q;
		m++;
	}
}

int pilalen;
int pila[100];

void
calc_vertices(int num)
{
	k[num].num_vertices = convex_hull(k[num].num_sites, k[num].sites);
	k[num].sites[k[num].num_vertices] = k[num].sites[0];
}

int
inside(int a, int b, int num)
{
	int result=1;
	int i;

	for(i=0; i<k[num].num_vertices; i++) {
		int v0x, v0y, v1x, v1y;

		v0x = (k[num].sites[i+1].x - k[num].sites[i].x);
		v0y = (k[num].sites[i+1].y - k[num].sites[i].y);
		v1x = (a - k[num].sites[i].x);
		v1y = (b - k[num].sites[i].y);
		if (v0x*v1y <= v0y*v1x) {
			result=0;
			break;
		}
	}
#if DEBUG
	printf("inside(%d,%d,%d)=%d\n", a, b, num, result);
#endif
	return result;
}

double
area(int num)
{
	int i;
	int a=0;

	for(i=1; i<=k[num].num_vertices; i++) {
		a += k[num].sites[i-1].x*k[num].sites[i].y;
		a -= k[num].sites[i].x*k[num].sites[i-1].y;
	}

	return ((double)a)/2;
}

#if DEBUG
void
display_kingdom(int num)		/* debug */
{
	int i;

	printf("\nKingdom #%d\n", num);
	printf("num_vertices: %d\n", k[num].num_vertices);
	for(i=0; i<k[num].num_sites; i++) {
		printf("SITE: %d %d\n", k[num].sites[i].x, k[num].sites[i].y);
	}
	printf("Area: %.2f\n", area(num));
}
#endif

int
main(void)
{
	int i,N;
	double tot_area=0.0;
	int num_k=0;

	while(1) {
		scanf("%d", &N);
		if (N==-1) {
			break;
		}
		if (N<3 || N>100) {
			abort();
		}
		k[num_k].light=1;
		k[num_k].num_sites=N;
		k[num_k].num_vertices=0;
		for(i=0; i<N; i++) {
			scanf("%d %d", &k[num_k].sites[i].x, &k[num_k].sites[i].y);
		}
		num_k++;
	}
	for(i=0; i<num_k; i++) {
		calc_vertices(i);
#if DEBUG
		display_kingdom(i);
#endif
	}
	while(1) {
		int a,b;
		if (scanf("%d %d", &a, &b) != 2) {
			break;
		}
		for(i=0; i<num_k; i++) {
			if (k[i].light && inside(a, b, i)) {
				tot_area += area(i);
				k[i].light = 0;
				/* break; */
			}
		}
	}
	printf("%.02f\n", tot_area);
#if DEBUG
	printf("\nResumen\n-------\n");
	for(i=0; i<num_k; i++) {
		printf("Kingdom %02d, light=%s, area=%5.2f\n", i, k[i].light ? "YES" : "NO ", area(i));
	}
#endif
	exit(0);
}