Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

The Doors

393.c

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

int walls;
float cha[20][5];

float dist[20][5];

float corte(float x1, float y1, float x2, float y2, float c)
{
	return (y1+(y2-y1)*(c-x1)/(x2-x1));
}

float linea(float x1, float y1, float x2, float y2)
{
	return sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));
}

int visible(int wall1, int pos1, int wall2, int pos2)
{
	int i;
	float x1, y1, x2, y2;

	if (wall1==-1) {
		x1=0.0;
		y1=5.0;
	} else {
		x1=cha[wall1][0];
		y1=cha[wall1][pos1];
	}
	x2=cha[wall2][0];
	y2=cha[wall2][pos2];
	for(i=wall1+1; i<wall2; i++) {
		float c=corte(x1, y1, x2, y2, cha[i][0]);
		if ((c<cha[i][1]) || (c>cha[i][4]) || ((c>cha[i][2]) && (c<cha[i][3]))) {
			return 0;
			break;
		}
	}
	return 1;
}

void calculate(void)
{
	int i,j,k,l;

	for(i=0; i<=walls; i++) {
		for(j=1; j<=4; j++) {
			if (visible(-1,0,i,j)) {
				dist[i][j] = linea(0.0, 5.0, cha[i][0], cha[i][j]);
			} else {
				float min=100000.0;
				for(k=0; k<i; k++) {
					for(l=1; l<=4; l++) {
						if (visible(k,l,i,j)) {
							float d = linea(cha[k][0], cha[k][l], cha[i][0], cha[i][j]);
							if (((d+dist[k][l]))<min) {
								min=d+dist[k][l];
							}
						}
					}
				}
				dist[i][j] = min;
			}
		}
	}
}

int main(void)
{
	char buf[1024];
	int i;

	while(fgets(buf, 1024, stdin)) {
		if (sscanf(buf, "%d", &walls)!=1) {
			exit(1);
		}
		if (walls==-1) {
			exit(0);
		}
		for(i=0; i<walls; i++) {
			if (!fgets(buf, 1024, stdin)) {
				exit(2);
			}
			if (sscanf(buf, "%f %f %f %f %f",
			    &cha[i][0], &cha[i][1], &cha[i][2], &cha[i][3],
			    &cha[i][4]) != 5) {
				exit(3);
			}
		}
		cha[walls][0]=10.0;
		cha[walls][1]=5.0;
		cha[walls][2]=5.0;
		cha[walls][3]=5.0;
		cha[walls][4]=5.0;
		calculate();
		printf("%.2f\n", dist[walls][1]);
	}
	exit(0);
}