createtriangle.c

1995年ACM contest FINAL试题和源码

/*

1995-96 ACM International Collegiate Programming Contest
Southwestern European Regional Contest
ETH Zurich, Switzerland
December 9, 1995


Problem: Triangle

Idea:			Berni Seybold, ETH Zurich
Implementation:	Manuel Bleichenbacher, Head Judge

Test set generation.

*/

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


const double cEps = 0.000001;
const double cUndefined = -1.0;

typedef enum {
	FALSE = 0,
	TRUE = 1
} bool;

typedef enum {
	errOk,
	errII,
	errMS
} ErrorState;

typedef double* Params;


FILE*	gFsol;
FILE*	gFin;
int gNumOfTriangles;

double pi;


void RandomTriangle ( Params p );
void RotateTriangle ( Params p, int rot );
void UndefineParams ( Params p, char* pat );
void CreateTriangle ( char* pat, int rot, ErrorState err, bool mayDestroy );
void CheckError ( Params p, char* pat, ErrorState *err);
void OutputSolution ( Params p, ErrorState err);
void OutputTriangle ( Params p);
void DestroyValue( Params p, int n );
void SRand(int seed);
int Rand();


void SRand(int seed)
{
	srand(seed);
}

int Rand()
{
	return rand() & 0x7fff;
}


void RandomTriangle ( Params p )
{
	double a, b, c, alpha, beta, gamma;

	do {
		a =	(double)Rand() * 100.0 / (double)0x7fff +
			(double)Rand() * 100.0 / (double)0x7fff / (double)0x7fff;
		b =	(double)Rand() * 100.0 / (double)0x7fff +
			(double)Rand() * 100.0 / (double)0x7fff / (double)0x7fff;
		c =	(double)Rand() * 100.0 / (double)0x7fff +
			(double)Rand() * 100.0 / (double)0x7fff / (double)0x7fff;
	} while ( a+b < c || a+c < b || b+c < a );
	
	alpha = acos( ( -a*a + b*b + c*c ) / ( 2.0 * b * c ) );
	beta =  acos( ( -b*b + c*c + a*a ) / ( 2.0 * c * a ) );
	gamma = acos( ( -c*c + a*a + b*b ) / ( 2.0 * a * b ) );
	
	assert( fabs( alpha + beta + gamma - pi ) < cEps * pi );
	
	p[0] = a; p[1] = alpha; p[2] = b;
	p[3] = beta; p[4] = c; p[5] = gamma;
}


void RotateTriangle ( Params p, int rot )
{
	double tmp1, tmp2;
	
	if (rot > 2) {		/* mirror triangle */
		tmp1 = p[2]; tmp2 = p[3];
		p[2] = p[4]; p[3] = p[5];
		p[4] = tmp1; p[5] = tmp2;
		rot -= 3;
	}
	
	while (rot > 0) {
		rot--;
		tmp1 = p[0]; tmp2 = p[1];
		p[0] = p[2]; p[1] = p[3];
		p[2] = p[4]; p[3] = p[5];
		p[4] = tmp1; p[5] = tmp2;
	}
}


void UndefineParams( Params p, char* pat )
{
	/* Pattern has special format:
		a, gamma, b, alpha, c, beta */
	
	if (pat[0] != 'x') p[0] = cUndefined;
	if (pat[1] != 'x') p[5] = cUndefined;
	if (pat[2] != 'x') p[2] = cUndefined;
	if (pat[3] != 'x') p[1] = cUndefined;
	if (pat[4] != 'x') p[4] = cUndefined;
	if (pat[5] != 'x') p[3] = cUndefined;
}


void DestroyValue( Params p, int n )
{
	double newValue;
	
	do {
		newValue =	(double)Rand() * 100.0 / (double)0x7fff +
					(double)Rand() * 100.0 / (double)0x7fff / (double)0x7fff;
	} while ( fabs( newValue - p[n] ) < cEps * newValue );
	p[n] = newValue;
}


void CheckError ( Params p, char* pat, ErrorState *err)
{
	if (*err == errMS) {
	
		/* Pattern has special format:
			a, gamma, b, alpha, c, beta */
		if ((pat[0] == '-' && pat[1] == 'x' && p[4] > p[2]) ||
			(pat[2] == '-' && pat[3] == 'x' && p[0] > p[4]) ||
			(pat[4] == '-' && pat[5] == 'x' && p[2] > p[0]) ||
			(pat[0] == '-' && pat[5] == 'x' && p[2] > p[4]) ||
			(pat[2] == '-' && pat[1] == 'x' && p[4] > p[0]) ||
			(pat[4] == '-' && pat[3] == 'x' && p[0] > p[2]))
			*err = errOk;
	}
}


void OutputSolution( Params p, ErrorState err)
{
	if ( err == errOk )
		fprintf( gFsol, "%0.10f %0.10f %0.10f %0.10f %0.10f %0.10f\n",
			p[0], p[1], p[2], p[3], p[4], p[5] );
	else if ( err == errII )
		fprintf( gFsol, "Invalid input.\n" );
	else if ( err == errMS )
		fprintf( gFsol, "More than one solution.\n" );
	else
		assert( FALSE );
}

void OutputTriangle( Params p)
{
	gNumOfTriangles++;
	fprintf( gFin, "%0.10f %0.10f %0.10f %0.10f %0.10f %0.10f\n",
		p[0], p[1], p[2], p[3], p[4], p[5] );
}


void CreateTriangle( char* pat, int rot, ErrorState err, bool mayDestroy )
{
	double	_p[6];
	double*	p = _p;
	int 	i;
	double	oldValue;
	
	/* create triangle */
	RandomTriangle( p );
	RotateTriangle( p, rot );
	
	/* original triangle */
	CheckError( p, pat, &err );
	OutputSolution( p, err );
	UndefineParams( p, pat );
	OutputTriangle( p );
	
	/* now destroy each defined value */
	if ( mayDestroy ) {
		assert( err == errOk );
		for (i = 0; i < 6; i++) {
			if (p[i] != cUndefined) {
			
				/* if all three angles are defined, then only destroy angles */
				if ( !( pat[1] == 'x' && pat[3] == 'x' && pat[5] == 'x' &&
					( i == 0 || i == 2 || i == 4 ) ) ) {
					oldValue = p[i];
					DestroyValue( p, i );
					OutputSolution( p, errII );
					OutputTriangle( p );
					p[i] = oldValue;
				}
			}
		}
	}
}


int main( int argc, char* argv[] )
{
	/* We just know there are xxx triangles to follow */

	const int	cNumOfExpectedTriangles = 888;
	int		i;
	
	SRand(30981);
	pi = atan(1) * 4.0;
	
	gFsol = fopen("triangle.sol", "w");
	assert( gFsol != 0 );
	gFin = fopen("triangle.in", "w");
	assert( gFsol != 0 );
	
	fprintf(gFin, "%d\n", cNumOfExpectedTriangles);
	
	gNumOfTriangles = 0;
	
	for (i=0; i < 6; i++) {
		CreateTriangle("xxxxxx", i, errOk, TRUE );	
		CreateTriangle("xxxxx-", i, errOk, TRUE );	
		CreateTriangle("xxxx-x", i, errOk, TRUE ); 
		CreateTriangle("xxxx--", i, errOk, TRUE ); 
		CreateTriangle("xxx-xx", i, errOk, TRUE ); 
		CreateTriangle("xxx-x-", i, errOk, TRUE ); 
		CreateTriangle("xxx--x", i, errOk, TRUE );
		CreateTriangle("xxx---", i, errOk, FALSE ); /* SAS */
		CreateTriangle("xx-xxx", i, errOk, TRUE );
		CreateTriangle("xx-xx-", i, errOk, TRUE );
		CreateTriangle("xx-x-x", i, errOk, TRUE );
		CreateTriangle("xx-x--", i, errOk, FALSE ); /* SAA */
		CreateTriangle("xx--xx", i, errOk, TRUE );
		CreateTriangle("xx--x-", i, errMS, FALSE ); /* SSA */
		CreateTriangle("xx---x", i, errOk, FALSE ); /* ASA */
		CreateTriangle("xx----", i, errII, FALSE );
		CreateTriangle("x-xxxx", i, errOk, TRUE );
		CreateTriangle("x-xxx-", i, errOk, TRUE );
		CreateTriangle("x-xx-x", i, errOk, TRUE );
		CreateTriangle("x-xx--", i, errMS, FALSE ); /* SSA */
		CreateTriangle("x-x-xx", i, errOk, TRUE );
		CreateTriangle("x-x-x-", i, errOk, FALSE ); /* SSS */
		CreateTriangle("x-x--x", i, errMS, FALSE ); /* ASS */
		CreateTriangle("x-x---", i, errII, FALSE );
		CreateTriangle("x--xxx", i, errOk, TRUE );
		CreateTriangle("x--xx-", i, errMS, FALSE ); /* ASS */
		CreateTriangle("x--x-x", i, errOk, FALSE ); /* AAS */
		CreateTriangle("x--x--", i, errII, FALSE );
		CreateTriangle("x---xx", i, errOk, FALSE ); /* SAS */
		CreateTriangle("x---x-", i, errII, FALSE );
		CreateTriangle("x----x", i, errII, FALSE );
		CreateTriangle("x-----", i, errII, FALSE );
		CreateTriangle("-xxxxx", i, errOk, TRUE );
		CreateTriangle("-xxxx-", i, errOk, TRUE );	
		CreateTriangle("-xxx-x", i, errOk, TRUE );
		CreateTriangle("-xxx--", i, errOk, FALSE ); /* ASA */
		CreateTriangle("-xx-xx", i, errOk, TRUE );
		CreateTriangle("-xx-x-", i, errMS, FALSE ); /* ASS */
		CreateTriangle("-xx--x", i, errOk, FALSE ); /* AAS */
		CreateTriangle("-xx---", i, errII, FALSE );
		CreateTriangle("-x-xxx", i, errOk, TRUE );
		CreateTriangle("-x-xx-", i, errOk, FALSE ); /* AAS */
		CreateTriangle("-x-x-x", i, errII, FALSE ); /* AAA */
		CreateTriangle("-x-x--", i, errII, FALSE );
		CreateTriangle("-x--xx", i, errOk, FALSE ); /* SAA */
		CreateTriangle("-x--x-", i, errII, FALSE );
		CreateTriangle("-x---x", i, errII, FALSE );
		CreateTriangle("-x----", i, errII, FALSE );
		CreateTriangle("--xxxx", i, errOk, TRUE );
		CreateTriangle("--xxx-", i, errOk, FALSE ); /* SAS */
		CreateTriangle("--xx-x", i, errOk, FALSE ); /* SAA */
		CreateTriangle("--xx--", i, errII, FALSE );
		CreateTriangle("--x-xx", i, errMS, FALSE ); /* SSA */
		CreateTriangle("--x-x-", i, errII, FALSE );
		CreateTriangle("--x--x", i, errII, FALSE );
		CreateTriangle("--x---", i, errII, FALSE );
		CreateTriangle("---xxx", i, errOk, FALSE ); /* ASA */
		CreateTriangle("---xx-", i, errII, FALSE );
		CreateTriangle("---x-x", i, errII, FALSE );
		CreateTriangle("---x--", i, errII, FALSE );
		CreateTriangle("----xx", i, errII, FALSE );
		CreateTriangle("----x-", i, errII, FALSE );
		CreateTriangle("-----x", i, errII, FALSE );
		CreateTriangle("------", i, errII, FALSE );
	}
	
	fclose(gFsol);
	fclose(gFin);
	
	/* printf("%d\n", gNumOfTriangles ); */
	assert( gNumOfTriangles == cNumOfExpectedTriangles );
	
	return 0;
}