import quickhull3d.*;
class Cell{
  Point3d centerPoint;
  ArrayList points;
  ArrayList randomDir;
  int[][] faceIndices;
  QuickHull3D hull;
  boolean insideCell;

  Cell(Point3d c){
    centerPoint=c;
    points=new ArrayList();
    randomDir=new ArrayList();
    hull=new QuickHull3D();
  insideCell=true;  
  }

  void add(Point3d p,Point3d d){
    points.add(p);
    randomDir.add(d); 
  }

  void clean(){
    ArrayList pointsOnHull=new ArrayList(); 
    for (int i = 0; i < hull.getNumFaces(); i++){
      int n=faceIndices[i].length;
      for (int j = 0; j<n; j++){ 
        if(!pointsOnHull.contains(points.get(faceIndices[i][j]))) pointsOnHull.add(points.get(faceIndices[i][j]));
      }
    }
    points.clear();
    points.addAll(pointsOnHull);
  }

  void getHull(){
    int n=points.size();
    Point3d[] constructionPoints=new Point3d[n];
    for(int i=0;i<n;i++){
      Point3d p=(Point3d)points.get(i);
      constructionPoints[i]=p;      
    }
    hull.build (constructionPoints);
    faceIndices = hull.getFaces( QuickHull3D.POINT_RELATIVE);
  }


  void grow(ArrayList centers){
    int n=points.size();
    double d2self, d2minother,f;
    int steps;
    insideCell=true;
    for(int i=0;i<n;i++){
      Point3d p=(Point3d)points.get(i);
      Point3d r=(Point3d)randomDir.get(i);
      d2self=sq(p.x-centerPoint.x)+sq(p.y-centerPoint.y)+sq(p.z-centerPoint.z);
      d2minother=findMinimumDistance2ToOtherPoints(i,centers);
      steps=0;
      while((d2minother>d2self)&&(inside(i))){
        steps++;
        p.x=centerPoint.x+steps*r.x;
        p.y=centerPoint.y+steps*r.y;
        p.z=centerPoint.z+steps*r.z;
        d2self=sq(p.x-centerPoint.x)+sq(p.y-centerPoint.y)+sq(p.z-centerPoint.z);
        d2minother=findMinimumDistance2ToOtherPoints(i,centers);
      }
      insideCell&=inside(i);
      if(inside(i)){
        f=1.0f+0.5f*(d2self-d2minother)/d2self;
        p.x=centerPoint.x+f*(p.x-centerPoint.x);
        p.y=centerPoint.y+f*(p.y-centerPoint.y);
        p.z=centerPoint.z+f*(p.z-centerPoint.z);
      }
    }

  }

  double findMinimumDistance2ToOtherPoints(int i,ArrayList centers){
    Point3d p=(Point3d)points.get(i);
    double d2=10000000000.0; 
    for(int j=0;j<centers.size();j++){      
      Point3d c=(Point3d)centers.get(j);
      if(sq(centerPoint.x-c.x)+sq(centerPoint.y-c.y)+sq(centerPoint.z-c.z)>0f){
        d2=min(d2,sq(p.x-c.x)+sq(p.y-c.y)+sq(p.z-c.z));
      }
    }
    return d2;

  }


  boolean inside(int i){
    Point3d p=(Point3d)points.get(i);
    return (p.x*p.x+p.y*p.y+p.z*p.z<90000f);//(p.x>=-300)&&(p.x<300)&&(p.y>=-500)&&(p.y<500)&&(p.z>=-300)&&(p.z<300);
  }


  void draw(){

    for (int i = 0; i < hull.getNumFaces(); i++)
    {     
      int n=faceIndices[i].length;

      beginShape();
      for (int j = 0; j <n; j++)    { 
        Point3d p=(Point3d)points.get(faceIndices[i][j]);
        vertex((float)p.x,(float)p.y,(float)p.z);
      }
      endShape(CLOSE);




    }


  }

}

double sq(double x){
  return x*x; 
}

double min(double x, double y){
  return (x>y)?y:x; 
}