/*********************************
 * Drawing the 120-cell Petrie Polygon
 * (C) 2008 Claudio Rocchini
 * CC-BY 3.0
 *********************************/

bool even_permutation( int p[], int n )
{
	int i,ns;
	int * pt = new int[n];
	for(i=0;i<n;++i) pt[i] = p[i];

	ns = 0;
	for(;;) {
		int j,k;
		for(j=0;j<n;++j) if(pt[j]!=j) break;
		if(j==n) break;
		for(k=0;k<n;++k) if(pt[k]==j) break;
		std::swap(pt[k],pt[j]);
		++ns;
	}
	delete[] pt;
	return ns%2==0;
}
void main()
{
	const double EPS = 1e-6;
	const int ND = 4;
	const int NV = 600; const int NE = 1200;
	const double fi  = (1+sqrt(5))/2; const double fi2  = fi*fi;
	const double rfi  = pow(fi,-1);   const double rfi2 = pow(fi,-2);
	double v[NV][ND]; int    e[NE][2];
	double px[NV]; double py[NV];
		// Magic numbers: hard to find projection directions
	const double PX[ND] = {-0.11317046518674401,-0.13682953481325594,-0.09854835601535949,-0.29133803200072961};
	const double PY[ND] = { 0.19601699561964564, 0.23699570627257371,-0.05689691987366302,-0.16820409120079699};

	int i,j,k,l;
	int i1,i2,i3,i4;

	k = 0;

	for(i1=   0;i1<4-1;++i1) for(i2=i1+1;i2<4  ;++i2)
	for(i3=0;i3<2;++i3) for(i4=0;i4<2;++i4) {
		v[k][ 0] = v[k][ 1] = v[k][ 2] = v[k][ 3] = 0;
		v[k][i1] = -2+4*i3;
		v[k][i2] = -2+4*i4;
		++k;
	}

	for(i1=0;i1<2;++i1) for(i2=0;i2<2;++i2)
	for(i3=0;i3<2;++i3) for(i4=0;i4<2;++i4) {
		v[k][0] = -1+2*i1; v[k][1] = -1+2*i2; v[k][2] = -1+2*i3; v[k][3] = i4==0 ? -sqrt(5) : sqrt(5); ++k;
		v[k][0] = -1+2*i1; v[k][1] = -1+2*i2; v[k][2] = i3==0 ? -sqrt(5) : sqrt(5); v[k][3] = -1+2*i4; ++k;
		v[k][0] = -1+2*i1; v[k][1] = i2==0 ? -sqrt(5) : sqrt(5); v[k][2] = -1+2*i3; v[k][3] = -1+2*i4; ++k;
		v[k][0] = i1==0 ? -sqrt(5) : sqrt(5); v[k][1] = -1+2*i2; v[k][2] = -1+2*i3; v[k][3] = -1+2*i4; ++k;;
	}

	for(i1=0;i1<2;++i1) for(i2=0;i2<2;++i2)
	for(i3=0;i3<2;++i3) for(i4=0;i4<2;++i4) {
		v[k][0] = i1==0?-fi:fi; v[k][1] = i2==0?-fi:fi; v[k][2] = i3==0?-fi:fi; v[k][3] = i4==0?-rfi2:rfi2; ++k;
		v[k][0] = i1==0?-fi:fi; v[k][1] = i2==0?-fi:fi; v[k][2] = i3==0?-rfi2:rfi2; v[k][3] = i4==0?-fi:fi; ++k;
		v[k][0] = i1==0?-fi:fi; v[k][1] = i2==0?-rfi2:rfi2; v[k][2] = i3==0?-fi:fi; v[k][3] = i4==0?-fi:fi; ++k;
		v[k][0] = i1==0?-rfi2:rfi2; v[k][1] = i2==0?-fi:fi; v[k][2] = i3==0?-fi:fi; v[k][3] = i4==0?-fi:fi; ++k;
	}

	for(i1=0;i1<2;++i1) for(i2=0;i2<2;++i2)
	for(i3=0;i3<2;++i3) for(i4=0;i4<2;++i4) {
		v[k][0] = i1==0?-rfi:rfi; v[k][1] = i2==0?-rfi:rfi; v[k][2] = i3==0?-rfi:rfi; v[k][3] = i4==0?-fi2:fi2; ++k;
		v[k][0] = i1==0?-rfi:rfi; v[k][1] = i2==0?-rfi:rfi; v[k][2] = i3==0?-fi2:fi2; v[k][3] = i4==0?-rfi:rfi; ++k;
		v[k][0] = i1==0?-rfi:rfi; v[k][1] = i2==0?-fi2:fi2; v[k][2] = i3==0?-rfi:rfi; v[k][3] = i4==0?-rfi:rfi; ++k;
		v[k][0] = i1==0?-fi2:fi2; v[k][1] = i2==0?-rfi:rfi; v[k][2] = i3==0?-rfi:rfi; v[k][3] = i4==0?-rfi:rfi; ++k;
	}

	double val[4]; int per[4];

	for(i1=0;i1<2;++i1) for(i2=0;i2<2;++i2) for(i3=0;i3<2;++i3) {
		val[0] = 0;
		val[1] = i1==0 ? -rfi2 : rfi2;
		val[2] = i2==0 ? -1 : 1;
		val[3] = i3==0 ? -fi2 : fi2;

		for(i=0;i<4;++i) per[i] = i;
		do {
			if(even_permutation(per,4)) { for(i=0;i<4;++i) v[k][i] = val[per[i]]; ++k; }
		} while(std::next_permutation(per,per+4));
	}

	for(i1=0;i1<2;++i1) for(i2=0;i2<2;++i2) for(i3=0;i3<2;++i3) {
		val[0] = 0;
		val[1] = i1==0 ? -rfi : rfi;
		val[2] = i2==0 ? -fi : fi;
		val[3] = i3==0 ? -sqrt(5) : sqrt(5);

		for(i=0;i<4;++i) per[i] = i;
		do {
			if(even_permutation(per,4)) { for(i=0;i<4;++i) v[k][i] = val[per[i]]; ++k; }
		} while(std::next_permutation(per,per+4));
	}

	for(i1=0;i1<2;++i1) for(i2=0;i2<2;++i2)
	for(i3=0;i3<2;++i3) for(i4=0;i4<2;++i4) {
		val[0] = i1==0 ? -rfi : rfi;
		val[1] = i2==0 ? -1 : 1;
		val[2] = i3==0 ? -fi : fi;
		val[3] = i4==0 ? -2 : 2;

		for(i=0;i<4;++i) per[i] = i;
		do {
			if(even_permutation(per,4)) { for(i=0;i<4;++i) v[k][i] = val[per[i]]; ++k; }
		} while(std::next_permutation(per,per+4));
	}
	assert(k==NV);

	const double de =  0.76393202250021019;
	k = 0;
	for(i=  0;i<NV-1;++i)
	for(j=i+1;j<NV  ;++j) {
		double d = 0;
		for(l=0;l<ND;++l) d += (v[i][l]-v[j][l])*(v[i][l]-v[j][l]);
		d = sqrt(d);
		if( fabs(de-d)<EPS ) { e[k][0] = i; e[k][1] = j; ++k; }
	}
	assert(k==NE);
	for(i=0;i<NV;++i){
		px[i] = 0; for(l=0;l<ND;++l) px[i] += v[i][l]*PX[l];
		py[i] = 0; for(l=0;l<ND;++l) py[i] += v[i][l]*PY[l];
	}
	
	const double SX = 800; const double SY = 800;
	const double B  = 32;  const double R  = 6;
	
	const double sca  = std::min((SX-2*B)/2,(SY-2*B)/2);
	for(i=0;i<NV;++i) { px[i] = B+(px[i]+1)*sca; py[i] = B+(py[i]+1)*sca; }

	FILE * fp = fopen("c:\\temp\\New120Cell.svg","w");
	fprintf(fp,
		"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n"
		"<svg\n"
		"xmlns:svg=\"http://www.w3.org/2000/svg\"\n"
		"xmlns=\"http://www.w3.org/2000/svg\"\n"
		"version=\"1.0\"\n"
		"width=\"%g\"\n" "height=\"%g\"\n"
		"id=\"New120Cell\">\n"
		,SX,SY
	);
	fprintf(fp,"<g style=\"stroke:#000000;stroke-width:2;stroke-opacity:0.6;\">\n");
	for(i=0;i<NE;++i)
		fprintf(fp,
			"<line x1=\"%5.1lf\" y1=\"%5.1lf\" x2=\"%5.1lf\" y2=\"%5.1lf\"/>\n"
			,px[e[i][0]],py[e[i][0]], px[e[i][1]],py[e[i][1]]
		);
	fprintf(fp,"</g>\n");
	fprintf(fp,"<g style=\"stroke:#000000;stroke-width:2;stroke-opacity:0.6;fill:#0080FF\">\n");
	for(i=0;i<NV;++i)
		fprintf(fp,"<circle cx=\"%5.1lf\" cy=\"%5.1lf\" r=\"%5.1lf\"/>\n",px[i],py[i],R);
	fprintf(fp,"</g>\n");
	fprintf(fp,"</svg>\n");
	fclose(fp);
}