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


/**The purpose of this routine is to extract the list
   of faces of an integer polyhedron (LongPolyhedron).
   The idea is that we consider all subsets of the vertex set,
   and accept those which satisfy 3 properties.
 
   -- the vertices are coplanar
   -- the vertices are on the boundary of P
   -- the set in question is a maximal set satisfying the first 2 properties.

   Suppose P has N vertices.  Then the subsets of P are encoded by the
   integers a=0,1,...,(2^N-1).  To extract the subset, we convert the
   integer a into binary and then include those members which correspond
   to a 1 digit. */

public class LongPolyFace {

    /*This gets the raw list of faces.  The subsets are
      not cyclically ordered.  We don't really use this
      routine in practice because, once we use it once,
      we are done with it.*/

    public static int[] faceList(LongPolyhedron P) {
	int N=P.count;
	int lim=(int)(Math.pow(2,N));
	int[] A=new int[lim];
	int count=0;
	   for(int i=0;i<lim;++i) {
	       LongVector[] V=getList(P,i);
	       if(isCoplanar(V)==true) {
		   if(isFace(P,V)==true) {
		   A[count]=i;
		   ++count;
		   }
	       }
	   }
	   int[] B=Combinatorics.copy(A,count);
	   B=Combinatorics.trim(N,B);
	   return(B);
    }




    /*This gets a subset of the points of a polyhedron*/

    public static LongVector[] getList(LongPolyhedron P,int a) {
	int N=P.count;
	int[] t=Combinatorics.binaryList(N,a);
	LongVector[] V=new LongVector[t.length];
	for(int i=0;i<t.length;++i) V[i]=P.V[t[i]];
	return(V);
    }

    /*This tests whether a list of vectors is coplanar*/

    public static boolean isCoplanar(LongVector[] V) {
	if(V.length<3) return(false);
	if(V.length==3) return(true);
	LongVector X=LongVector.normal(V);
	
	long test0=LongVector.dot(X,V[0]);
	for(int i=0;i<V.length;++i) {
	    long test=LongVector.dot(X,V[i]);
	    if(test!=test0) return(false);
	}
	return(true);
    }


    /*This tests whether a list of vectors is contained 
      in a face of the polyhedron*/

    public static boolean isFace(LongPolyhedron P,LongVector[] V) {
	LongVector X=LongVector.normal(V);
	long[] m=LongPolyCombinatorics.range(X,P);
	long min=m[0];
	long max=m[1];
	long target=LongVector.dot(X,V[0]);
	if(max<=target) return(true);
	if(min>=target) return(true);
	return(false);
    }




    public static void checkBad(LongPolyhedron P) {
	int v=P.count;
	for(int i=0;i<v;++i) {
	    for(int j=i+1;j<v;++j) {
		for(int k=j+1;k<v;++k) {
		    boolean test=checkBad(P,i,j,k);
		}
	    }
	}
    }



    public static boolean checkBad(LongPolyhedron P,int i,int j,int k) {
	LongVector[] V={P.V[i],P.V[j],P.V[k]};
	LongVector X=LongVector.normal(V);
	long t=LongVector.dot(X,X);
	if(t!=0) return(false);

	Vector V0=new Vector(V[0]);
	Vector V1=new Vector(V[1]);
	Vector V2=new Vector(V[2]);

	double d01=Vector.dist(V0,V1);
	double d12=Vector.dist(V1,V2);
	double d20=Vector.dist(V2,V0);

	if(d01>d12+d20-.00000001) System.out.println("bad  "+k);
	if(d12>d20+d01-.00000001) System.out.println("bad  "+i);
	if(d20>d01+d12-.00000001) System.out.println("bad  "+j);
	return(true);
    }




}