import java.applet.Applet;
import java.awt.*;
import java.awt.event.*;
import java.applet.*;
import java.awt.geom.*;
import java.math.*;


public class Polytope {
    int count;
    Vector4[] V=new Vector4[20];
    int[] type=new int[4];

    public Polytope() {}

    public Polytope(Polytope P) {
	count=P.count;
	for(int i=0;i<P.count;++i) {
	    V[i]=P.V[i];
	}
	type[0]=P.type[0];
	type[1]=P.type[1];
	type[2]=P.type[2];
    }

    public static Polytope reflect(Polytope P) {
	Polytope Q=new Polytope();
	Q.count=P.count;
	double A=0;
	double z=0;
	for(int i=0;i<P.count;++i) {
	    A=P.V[i].x[3];
	    Q.V[i]=new Vector4(1+A-P.V[i].x[0],1+A-P.V[i].x[1],1-P.V[i].x[2],P.V[i].x[3]);
	}
	Q.type[0]=1-P.type[0];
	Q.type[1]=-P.type[1];
	Q.type[2]=-P.type[2];
	return(Q);
    }



    public static Polytope shift(Vector4 V,Polytope P) {
	Polytope Q=new Polytope();
	for(int i=0;i<P.count;++i) {
	    Q.V[i]=Vector4.plus(P.V[i],V);
	}
	Q.count=P.count;
	Q.type[0]=P.type[0];
	Q.type[1]=P.type[1];
	Q.type[2]=P.type[2];
	return(Q);
    }




    public static int match(Polytope P1,Polytope P2) {
	int test=0;
	int count=0;
	for(int i=0;i<P1.count;++i) {
	    test=0;
	    for(int j=0;j<P2.count;++j) {
		if(Vector4.dist2(P1.V[i],P2.V[j])<.000001) test=1;
	    }
	    if(test==1) ++count;
	}
	return(count);
    }









    /**this is the action of the lattice on polytopes.  The lattice is the one in
       my monograph.  It is a discrete Abelian group generated by three elements
       gamma1,gamma2,gamma3*/

    public static Polytope gamma1(int q,Polytope P) {
	Polytope Q=new Polytope();
	Q.count=P.count;
	for(int i=0;i<P.count;++i) {
	    Q.V[i]=Vector4.plus(P.V[i],new Vector4(q*P.V[i].x[3]+q,0,0,0));
	}
	Q.type[0]=P.type[0];
	Q.type[1]=P.type[1];
	Q.type[2]=P.type[2];
	return(Q);
    }

    public static Polytope gamma2(int q,Polytope P) {
	Polytope Q=new Polytope();
	Q.count=P.count;
	for(int i=0;i<P.count;++i) {
	    Q.V[i]=Vector4.plus(P.V[i],new Vector4(-q*P.V[i].x[3]+q,q*P.V[i].x[3]+q,0,0));
	}
	Q.type[0]=P.type[0];
	Q.type[1]=P.type[1];
	Q.type[2]=P.type[2];
	return(Q);
    }

    public static Polytope gamma3(int q,Polytope P) {
	Polytope Q=new Polytope();
	Q.count=P.count;
	for(int i=0;i<P.count;++i) {
	    Q.V[i]=Vector4.plus(P.V[i],new Vector4(-q,-q,q,0));
	}
	Q.type[0]=P.type[0];
	Q.type[1]=P.type[1];
	Q.type[2]=P.type[2];
	return(Q);
    }

    public static Polytope gamma(int q1,int q2,int q3,Polytope P) {
	Polytope Q=new Polytope(P);
	Q=gamma1(q1,Q);
	Q=gamma2(q2,Q);
	Q=gamma3(q3,Q);
	return(Q);
    }







    /*Taking a planar slice.  We consider the vertices of the polytope P three at a
      time, as indicated by the indices i,j,k.  Then we compute where the triangle
      with vertices P.V[i],P.v[i],P.v[k] intersects the plane of the slice.
      If the intersection is empty, we return (null). 
      The plane of the slice is specified by the pair (x,y), and the vectors
      V[0],V[1]. Once we find the point of intersection, we project it into another
      plane using the vectors V[2],V[3].       When we have these points for every triple, 
      we take the convex hull.*/

    public static Complex planarSlice0(Vector4[] V,double x,double y,Polytope P,int i,int j,int k) {
	double x0=V[0].dot(V[0],P.V[i]);
	double y0=V[1].dot(V[1],P.V[i]);
	double x1=V[0].dot(V[0],P.V[j]);
	double y1=V[1].dot(V[1],P.V[j]);
	double x2=V[0].dot(V[0],P.V[k]);
	double y2=V[1].dot(V[1],P.V[k]);	
        double det=x1*y0 + x2*y1 + x0*y2 - x0*y1 - x1*y2 - x2*y0;
	if(Math.abs(det)<.000001) return(null);
	double r=y*x1 - y*x2 + x2*y1 - x1*y2 - y1*x + y2*x;
	double s=y*x0 - y*x2 + x2*y0 - x0*y2 - y0*x + y2*x;
	r=r/det;
	s=-s/det;
	if(r<0.0000001) return(null);
	if(r>0.9999999) return(null);
	if(s<0.0000001) return(null);
	if(s>0.9999999) return(null);
	if(r+s>.9999999) return(null);
	Complex p=new Complex();
	x0=V[2].dot(V[2],P.V[i]);
	y0=V[3].dot(V[3],P.V[i]);
	x1=V[2].dot(V[2],P.V[j]);
	y1=V[3].dot(V[3],P.V[j]);
	x2=V[2].dot(V[2],P.V[k]);
	y2=V[3].dot(V[3],P.V[k]);
	p.x=r*x0+s*x1+(1-r-s)*x2;
	p.y=r*y0+s*y1+(1-r-s)*y2;
	return(p);
    }


    public static Complex[] planarSlice1(Vector4[] V,double x,double y,Polytope P) {
	GeneralPath gp=new GeneralPath();
	int fred=0;
	Complex p;
	Complex[] zz=new Complex[100];
	int number=0;

	for(int i=0;i<P.count;++i) {
	    for(int j=i+1;j<P.count;++j) {
		for(int k=j+1;k<P.count;++k) {

		    p=planarSlice0(V,x,y,P,i,j,k);
		    if(p!=null) {
			++number;
			zz[number]=new Complex(p);
		    }
		}
	    }
	}
	zz[0]=new Complex(number,0);
	return(zz);
    }



    public static GeneralPath planarSlice(Vector4[] V,double x,double y,Polytope P){
	GeneralPath gp=new GeneralPath();
	Complex[] zz=planarSlice1(V,x,y,P);
	int n=(int)(zz[0].x);
	   if(n>0) {
	   PolyWedgeLong LP=new PolyWedgeLong(n,zz);
	   LP=PolyWedgeLong.cheapHull(LP);
	   gp=LP.toGeneralPath();
	}
	return(gp);
    }







    public GeneralPath slice0(double x,double y) {
	Vector4[] V=new Vector4[4];
	V[0]=new Vector4(0,0,1,0);
	V[1]=new Vector4(0,0,0,1);
	V[2]=new Vector4(1,0,0,0);
	V[3]=new Vector4(0,1,0,0);
	return(planarSlice(V,x,y,this));
    }



    //for hexagrid theorem 1
    public GeneralPath slice1(double y,double A) {
	Vector4[] V=new Vector4[4];
	V[0]=new Vector4(0,1,-1,0);
	V[1]=new Vector4(0,0,0,1);
	V[2]=new Vector4(1,0,0,0);
	V[3]=new Vector4(0,0,1,0);
	return(planarSlice(V,y+.00001,A+.00001,this));
    }

    //for hexagrid theorem 2
    public GeneralPath slice2(double x,double y) {
	Vector4[] V=new Vector4[4];
	V[0]=new Vector4(1,1,0,0);
	V[1]=new Vector4(0,0,0,1);
	V[2]=new Vector4(1,0,0,0);
	V[3]=new Vector4(0,0,1,0);
	return(planarSlice(V,x+.00001,y,this));
    }
















    public void print(Output OUT) {
        OUT.write("SLASHlefteqn{");   //start equation
	for(int i=0;i<count;++i) {
	    OUT.write("SLASHleft[SLASHmatrix{");
	    int a0=(int)(V[i].x[0]);
	    int a1=(int)(V[i].x[1]);
	    int a2=(int)(V[i].x[2]);
	    int a3=(int)(V[i].x[3]);
	    OUT.write(a0+" SLASHcr "+a1+" SLASHcr "+a2+" SLASHcr "+a3+"}");
  	    OUT.writeln("SLASHright]");
	    if(i<count-1) OUT.write("SLASHhskip 5 pt");
	}   

            OUT.write("SLASHhskip 20 pt ");
            Integer A1=new Integer(type[1]);
	    Integer A2=new Integer(type[2]);
	    OUT.write("("+A1.toString()+",");
	    OUT.write(A2.toString()+")");

	    OUT.writeln("}");    //end equation
	System.out.println("");
    }

    public void simplePrint() {
	System.out.println("------------");
	System.out.println("type "+type[1]+" "+type[2]);
	for(int i=0;i<count;++i) {
	    int a0=(int)(V[i].x[0]);
	    int a1=(int)(V[i].x[1]);
	    int a2=(int)(V[i].x[2]);
	    int a3=(int)(V[i].x[3]);
	    System.out.println(a0+" "+a1+" "+a2+" "+a3);
	}
	System.out.println("------------");
    }



    //return of 1 means disjoint

    public static int testDisjoint(Polytope P1,Polytope P2) {
	Vector4 V=new Vector4();
	double test=0;
	int lim=2;
	for(int i1=-lim;i1<=lim;++i1) {
	for(int i2=-lim;i2<=lim;++i2) {
	for(int i3=-lim;i3<=lim;++i3) {
	for(int i4=-lim;i4<=lim;++i4) {
	    if(i1*i1+i2*i2+i3*i3+i4*i4>0) {
	    V=new Vector4(i1,i2,i3,i4);
	    test=testDisjoint0(V,P1,P2);
	    if(test==1) return(1);
	    }
	}
	}
	}
	}
	return(0);
    }



    //return of 1 means disjoint

    public static int testDisjoint0(Vector4 V,Polytope P1,Polytope P2) {

	double min1,max1,min2,max2;
	min1=10000;
	min2=10000;
	max1=-10000;
	max2=-10000;

	double test=0;
	for(int i=0;i<P1.count;++i) {
	    test=Vector4.dot(V,P1.V[i]);
	    if(min1>test) min1=test;
	    if(max1<test) max1=test;
	}

	for(int i=0;i<P2.count;++i) {
	    test=Vector4.dot(V,P2.V[i]);
	    if(min2>test) min2=test;
	    if(max2<test) max2=test;
	}

	int good=0;
	if(min1>=max2) good=1;
	if(min2>=max1) good=1;
	if(good==1)  {
                 return(1);
	}
	return(0);
    }


    /**This routine counts the number of vertices in the hyperplane normal to the vector
       (1,1,0,-1).  This is the hyperplane Pi in part III of the book. if the polytope
       actually intersects the hyperplane, the return is -1.  Also, if the polytope
       lies on the negative side of Pi then the return is -1.  By this we mean that
       v0+v1-v3<=0 for all vertices*/



    public static int countHyperplaneIntersect(Polytope P) {
	Polytope Q=hyperplaneIntersect(P);
	if(Q!=null) 	return(Q.count);
	return(0);
    }



    public static Polytope hyperplaneIntersect(Polytope P) {
	int count=0;
	double test=0;
	int neg=0;
	int pos=0;
	Vector4[] TEMP=new Vector4[10];
	for(int i=0;i<P.count;++i) {
	    test=P.V[i].x[0]+P.V[i].x[1]-P.V[i].x[3];
	    if(test*test<.00000001) {
		TEMP[count]=new Vector4(P.V[i]);
                  ++count;
	    }
	    if(test>.00001) pos=1;
	    if(test<-.00001) neg=1;
	}
	if(neg==1) return(null);
	if(count==0) return(null);
	Polytope Q=new Polytope();
	Q.count=count;
	for(int i=0;i<count;++i) Q.V[i]=new Vector4(TEMP[i]);
	Q.type[1]=P.type[1];
	Q.type[2]=P.type[2];
	return(Q);
    }






}