/*
 * Onion algorithm
 */

// NOTE : it would be more efficient to precompute the sines and cosines.

import java.util.*;

public class Onion {

    Vector chain,newChain,active; /* vertex chains */
    Vector room; /* list of faces */
    Vector vertices; /* list of vertices */
    Vector segments;

    public int p; /* p-gons */
    public int q; /* q of each per vertex */

    public double radius1; /* distance from vertex to face center */
    public Complex[] based;

    public int myMod(int a, int b) {
	return( (a>=0) ? (a % b) : (b-1+((a+1) % b)) );
    }

    public class Segment {
	Vertex v1,v2;
	Face f1,f2;
	boolean isOpen;
	public Segment(Vertex a, Vertex b, Face c, Face d) {
	    v1=a;
	    v2=b;
	    f1=c;
	    f2=d;
	    segments.add(this);
	}
    }

    public class Vertex {
	Vertex[] neighbor; /* ordered list of neighboring vertices */
	Face[] face; /* ordered list of faces sharing this vertex */
	int[] ownIndex; /* what is the index of this vertex in the corresponding face */
	int faceCount; /* How many existing faces share this vertex */
	boolean visited;
	Segment[] segment;
	Complex z;
	/* Constructor */
	public Vertex() {
	    neighbor=new Vertex[q];
	    face=new Face[q];
	    segment=new Segment[q];
	    ownIndex=new int[q];
	    faceCount=0;
	    vertices.add(this);
	}
	public Face getFace(int i) {
	    return(face[myMod(i,q)]);
	}
	public int getOwnIndex(int i) {
	    return(ownIndex[myMod(i,q)]);
	}
	public Segment getSegment(int i) {
	    return(segment[myMod(i,q)]);
	}
	public Face getFaceAfterVertex(int i) {
	    return(face[myMod(i+1,q)]);
	}
	public Face getFaceBeforeVertex(int i) {
	    return(face[myMod(i,q)]);
	}
	public Vertex getVertexAfterFace(int i) {
	    return(neighbor[myMod(i,q)]);
	}
	public Vertex getVertexBeforeFace(int i) {
	    return(neighbor[myMod(i-1,q)]);
	}
    }

    /*
    public class OrientedSegment {
	Vertex v;
	int end;
	public OrientedSegment(Vertex w, int e) {
	    v=w;
	    end=e;
	}
    }

    public Vertex getEnd(OrientedSegment s) {
	return(getNeighbor(s.v,s.end));
    }
    */

    public class Face {
	Face[] neighbor;
	Vertex[] vertex;
	int[] ownIndex; /* what is the index of this face in the corresponding vertex */
	Segment[] segment;
	/* Constructor */
	public Face() {
	    neighbor=new Face[p];
	    vertex=new Vertex[p];
	    segment=new Segment[p];
	    ownIndex=new int[p];
	    room.add(this);
	}
	public Vertex getVertex(int i) {
	    return(vertex[myMod(i,p)]);
	}
	public int getOwnIndex(int i) {
	    return(ownIndex[myMod(i,p)]);
	}
	public Segment getSegment(int i) {
	    return(segment[myMod(i,p)]);
	}
	public Vertex getVertexAfterFace(int i) {
	    return(vertex[myMod(i+1,p)]);
	}
	public Vertex getVertexBeforeFace(int i) {
	    return(vertex[myMod(i,p)]);
	}
	public Face getFaceAfterVertex(int i) {
	    return(neighbor[myMod(i,p)]);
	}
	public Face getFaceBeforeVertex(int i) {
	    return(neighbor[myMod(i-1,p)]);
	}
    }

    /* Returns the face touching the segment from
     * vertex k to k+1 of face f. Assumes the vertex/faces structure
     * is correctly linked.
     */
    public Face findNeighbor(Face f, int k) {
	Vertex v=f.getVertex(k);
	return(v.getFace(f.getOwnIndex(k)-1));
    }

    public int findNeighborIndex(Face f, int k) {
	Vertex v=f.getVertex(k);
	return(myMod(v.getOwnIndex(f.getOwnIndex(k)-1)-1,p));
    }

    /* Returns the vertex at the end of the segment from
     * face k to k+1 of vertex v. Assumes the vertex/faces structure
     * is correctly linked.
     */
    public Vertex findNeighbor(Vertex v, int k) {
	Face f=v.getFace(k);
	if(f==null) {
	    f=v.getFace(k+1);
	    if(f==null) return(null);
	    return(f.getVertex(v.getOwnIndex(k+1)+1));
	}
	return(f.getVertex(v.getOwnIndex(k)-1));
    }

    public void growOnce() {
	int initialChainLenght=chain.size();
	newChain=new Vector();

	for(int n=0; n<initialChainLenght; n++) {
	    saturateVertex(n);
	}

	chain=newChain;
    }

    public void saturateVertex(int n) {
	for(int j=0; j<q; j++) {
	    if(((Vertex) chain.elementAt(n)).face[j]==null) {
		addFaceToVertex(n,j);
	    }
	}
    }

    public void argh() {
	System.out.println("Argh !");
	System.exit(-1);
    }

    /*
     * Link face f to vertex v
     * i is the index of f in v
     * j is the index of v in f
     */
    public void link(Vertex v, int i, Face f, int j) {
	f.vertex[j]=v;
	v.ownIndex[i]=j;
	v.face[i]=f;
	f.ownIndex[j]=i;
	v.faceCount++;
    }
   
    public void addFaceToVertex(int n, int j) {

	Vertex v=(Vertex) chain.elementAt(n);

	// First, check that the slot is empty
	if(v.face[j]!=null) argh(); // this should not happen

	// Create the object and add it to the global list of faces
	Face newFace=new Face();

	// Link the vertex and the face
	link(v,j,newFace,0);

	// Sew the boundary of the new face (iteratively)

	// For this work, there must be no "hole" in the structure
	Vertex w;
	Face f2;
	int t,k,m,j2;

	// scan forward
	t=0;
	j2=j;
	w=v;
	f2=w.getFace(j2-1);
	for(;f2!=null && t<p-1;) {
	    k=myMod(v.ownIndex[myMod(j2-1,q)]-1,p);
	    j2=myMod(f2.ownIndex[k]-1,q);
	    w=f2.vertex[k];
	    t++;

	    link(w,j2,newFace,t);

	    f2=w.face[myMod(j2-1,q)];
	}


	// scan backward
	int t2;
	t2=0;
	j2=j;
	w=v;
	f2=w.face[(j2+1) % q];
	for(;f2!=null && t2>1-p;) {
	    k=(w.ownIndex[(j2+1) % q]+1) % p;
	    j2=(f2.ownIndex[k]+1) % q;
	    w=f2.vertex[k];
	    t2--;

	    link(w,j2,newFace,myMod(t2,p));

	    f2=w.face[(j2+1) % q];
	}


	// test whether more than all vertices of the new polygon were sewed
	if(1+t-t2>p) argh(); // should not happen

	/* Now, we add the missing vertices and udpate the chain */
	// First, compute the coordinate of the center of the face
	// For this, find a face
	int k0=0;	
	Face f=v.getFace(k0);
	for( ; k0<p && f==null; ) { k0++; f=v.getFace(k0); }
	// Get a vertex
	w=f.getVertex(v.getOwnIndex(k0)-1);
	// This is the k-neighbor of v
	// Compute position of the center
	Complex aux;
	aux=phi(v.z.opposite(),w.z);
	aux=aux.mul(radius1/Math.sqrt(aux.norm()));
	Complex center=phi(v.z,aux.rotate((j-k0-0.5)/(double) q));
	aux=phi(center.opposite(),v.z);
	aux=aux.mul(radius1/Math.sqrt(aux.norm()));
	for(int i=t+1; i<=p+t2-1; i++) {
	    w=new Vertex();
	    /* Let's determine its z-coordinate */
	    w.z=phi(center,aux.rotate((i-0)/(double) p));
	    link(w,0,newFace,i);
	    newChain.add(w);
	}
    }

    /*
     * phi(a,z) = (a+z)/(1+conj(a).z)
     */
    public Complex phi(Complex z0, Complex z) {
	double ax,ay,bx,by,d;
	ax=z0.re+z.re;
	ay=z0.im+z.im;
	bx=1+z0.re*z.re+z0.im*z.im;
	by=z0.re*z.im-z0.im*z.re;
	d=bx*bx+by*by;
	return(new Complex((ax*bx+ay*by)/d,
			   (ay*bx-ax*by)/d));
    }

    public void germ() {
	chain=new Vector();
	room=new Vector();
	vertices=new Vector();
	segments=new Vector();
	Face f=new Face();
	for(int i=0; i<p; i++) {
	    Vertex v=new Vertex();
	    link(v,0,f,i);
	    chain.add(v);
	    v.z=(new Complex(radius1,0)).rotate(i/(double) p);
	}
    }

    /* This one assumes the vertex/faces structure
     * is correctly linked.
     */
    public void linkEverybody() {
	Iterator i;
	/* We link faces to faces */
	Face f,f2;
	Segment s;
	for(i=room.iterator();i.hasNext();) {
	    f=(Face) i.next();
	    for(int j=0; j<p; j++) {
		f2=findNeighbor(f,j);
		f.neighbor[j]=f2;
		// And create segments
		if(f2!=null) {
		    if(f.segment[j]==null) {
			int k=findNeighborIndex(f,j);
			s=new Segment(f.getVertex(j),f.getVertex(j+1),f,f2);
			f.segment[j]=s;
			f2.segment[k]=s;
		    }
		}
		else {
		    f.segment[j]=new Segment(f.getVertex(j),f.getVertex(j+1),f,null);
		}
	    }
	}
	/* We link vertices to vertices and link segments to them */
	Vertex v,v2;
	for(i=vertices.iterator();i.hasNext();) {
	    v=(Vertex) i.next();
	    for(int j=0; j<q; j++) {
		v2=findNeighbor(v,j);
		v.neighbor[j]=v2;
		if(v2!=null) {
		    f=v.getFace(j);
		    if(f!=null) {
			v.segment[j]=f.getSegment(v.getOwnIndex(j)-1);
		    }
		    else {
			f=v.getFace(j+1);
			v.segment[j]=f.getSegment(v.getOwnIndex(j+1));
		    }
		}
		else {
		    v.segment[j]=null;
		}
	    }
	}
    }


    public void activateSegments(Vertex v) {
	Vertex w;
	for(int j=0; j<q; j++) {
	    w=v.neighbor[j];
	    if(w!=null) {
		if(!w.visited) active.add(v.getSegment(j));
	    }
	}
    }

    public void generateMaze() {
	Iterator i;
	/* Let's set every door open */
	for(i=segments.iterator();i.hasNext();) {
	    ((Segment) i.next()).isOpen=true; 
	}
	/* Let's set every vertex unvisited */
	for(i=vertices.iterator();i.hasNext();) {
	    ((Vertex) i.next()).visited=false; 
	}
	/* Let's visit every vertex on the boundary
	 * and close every door on the boundary */
	Vertex v;
	for(i=chain.iterator();i.hasNext();) {
	    v=(Vertex) i.next();
	    v.visited=true;
	    for(int j=0; j<q; j++) {
		if(v.getFace(j)!=null && v.getFace(j+1)==null) {
		    v.getSegment(j).isOpen=false;
		}
		/*
		if(v.getFace(j)==null && v.getFace(j+1)!=null) {
		    v.getSegment(j).isOpen=false;
		}
		*/
	    }
	}
	/* Activate the segments (we scan the chain once again) */
        // NOTE : WE MAY ADD SOME SEGMENTS TWICE TO THE active LIST
	// THIS IS NO PROBLEM SINCE THIS SEMGENT WILL JUST BE REMOVED LATER
	active=new Vector();
	for(i=chain.iterator();i.hasNext();) {
	    activateSegments((Vertex) i.next());
	}
	/* Let's grow the maze */
	/* princip: we keep tract of visisted vertices and maintain a
	 * list of active (oriented) segments. We grow randomly on this list.
	 * We stop when no segment is active any more.
	 * Such segments are based on visited vertices and point on
	 * unvisited ones. All such pairs are supposed to be in the list
	 */
	int length,j;
	Segment s;
	length=active.size();
	for(;length>0;) {
	    // choose a random segment 's'
	    j=(int) Math.floor(Math.random()*length);
	    s=(Segment) active.elementAt(j);
	    // if its end is visited then we just remove the segment
	    // from the list (this is a bit inelegant but...)
    /*	    System.out.print("segment "+String.valueOf(j)+" sur "
	      +String.valueOf(length)+" ");
	    System.out.println((s==null ? "pas d's": "s existe")+" ");
	    System.out.println((s.v1==null ? "0": "1")+" "+
	      (s.v2==null ? "0": "1"));
	    System.out.flush();
     */
	    if(s.v1.visited && s.v2.visited) {
		// Do nothing
	    }
	    else {
		if(s.v1.visited) {v=s.v2;}
		else {v=s.v1;}
		v.visited=true;
		// and set the segment as closed
		s.isOpen=false;
		// and visit new ones
		activateSegments(v);
	    }
	    // remove the segment from the list of active ones
	    active.removeElementAt(j);
	    //
	    length=active.size();
	}
    }

    public void computeConstants() {
	radius1=Math.sqrt(
	        Math.cos(Math.PI*(1.0/p+1.0/q))
               /Math.cos(Math.PI*(1.0/p-1.0/q))
		);
	based=new Complex[p];
	
    }

    public void doAll(int pp, int qq, int n) {
	p=pp;
	q=qq;
	computeConstants();
	germ();
	for(int i=0; i<n; i++) growOnce();
	linkEverybody();
	generateMaze();
    }
}