import java.awt.*;
public class K_Driven{

  final double PARAM=0.05;
  int error=0;
  double ww,hh;
  double mindis=1000.0;
  double minspeed=1000.0;
  int numberofpoint=0;
  int numberofextreme=0;
  int firstnumofp=0;
  Vertex Head;
  Vertex Tail;
  double scale=100.0;
  double kmin = 0.1;
  double kmax = 0.1;
  double Level = 0.1;
  double High = 50.0; 
  double Low = 30.0;
  double Low2 = 5.0;
  Double checker;
 public  K_Driven()
    {
      this.listinitialize();
    }
  public K_Driven(int ww,int hh)
    {
      this.listinitialize();
      
    }
  public void listinitialize()
    {
      double nx,ny;
      System.gc();
      numberofpoint=0;
      
      mindis=1000.0;
      minspeed=1000.0;
      
      numberofextreme=0;
      kmin = 0.1;
      kmax = 0.1;
      checker = new Double(0.0);
      
      firstnumofp=0;
      Head = new Vertex();
      Tail = new Vertex();
      Init(Head,Tail);
    }
 
  public double setkmin(double dkm){
    kmin = dkm;
    return 0.0;
  }
  public void setnumext(int dnx){
    numberofextreme = dnx;
  }
  public double getkmin(){
    return kmin;
  }
 
  private boolean NearV(Vertex v1,Vertex v2){
   /* float v1x,v1y,v2x,v2y;
    v1x = ((float)(v1.x));
    v1y = ((float)(v1.y));
    v2x = ((float)(v2.x));
    v2y = ((float)(v2.y)); */
    int v1x,v1y,v2x,v2y;
    v1x = ((int)((double)(scale*v1.x)));
    v1y = ((int)((double)(scale*v1.y)));
    v2x = ((int)((double)(scale*v2.x)));
    v2y = ((int)((double)(scale*v2.y)));
    if((v1x==v2x)&&(v1y==v2y)){
      return true;
    }else{
      return false;
    }
  }
  private int repamameter(int minpoints){
 double dumx,dumy;
	Vertex dummy;
	Vertex now = Head;
	while(next(now)!=Tail){
	    now  = next(now);
	     if(next(now)==Tail)break;
	     if(next(now).extreme!=1){
	       DeleteN(now);
	      numberofpoint--;
	     }
	     if(next(now)==Tail)break;
	}
	if(next(now)==Tail){
	  if(next(Head).extreme!=1){
	    dummy = next(next(Head));
	    Head.next = dummy;
	    dummy.back = Head; 
	    numberofpoint--;
	  }
	}
	
    return 0;
  } 
public int UpdateforKn1(){
    
    UpdateProperty();
    
    double dx,dy,speed;
    double epcilon;
    
    Vertex now = next(Head);
    epcilon = ((mindis)/(firstnumofp));
    now = Head;
    DoubleVector grad = new DoubleVector(0.0,0.0);;
    while(next(now)!=Tail){
      now = next(now);
      speed = now.k;
      dx = now.x +epcilon*(speed*now.normal.x);
      dy = now.y +epcilon*(speed*now.normal.y);
      now.time = new DoubleVector(now.x,now.y);
      now.x = dx;
      now.y = dy;
      if(checker.isNaN(now.x)||checker.isNaN(now.y)){
	System.out.println("now.x = "+now.x+" now.y = "+now.y);
	return 2;
      }
    }
    int backt=0;
    while(backt!=numberofpoint){
      if(numberofpoint<=11){
	return 1;
      }
      backt = numberofpoint;
       reparameterization();
        if(numberofpoint<=11){
	return 1;
      }
    }
    if(numberofpoint>8){
      if(numberofpoint<=11)return 1;
      return 0;
    }else{
      return 1;
    }
    
  } 
  public int UpdateforKn2(double constvC,double constvD){
    
    UpdateProperty();
    
    double dx,dy,speed;
    double epcilon;
    dx = 0.0;
    dy = 0.0;
    speed = 0.0;
    Vertex now = next(Head);
    /*
    if(mindis<0.001){
      epcilon = (0.001/(firstnumofp));
    }else{
      epcilon = ((mindis)/(firstnumofp));
    }
    */
    epcilon = ((mindis)/(firstnumofp));
    double nsize=0.0;
    now = Head;
    DoubleVector grad = new DoubleVector(0.0,0.0);;
    while(next(now)!=Tail){
      now = next(now);
      speed = constvC + constvD*now.k;
      
      dx = now.x + epcilon*(speed*now.normal.x);
      dy = now.y + epcilon*(speed*now.normal.y);
      now.time = new DoubleVector(now.x,now.y);
      now.x = dx;
      now.y = dy;
       if(checker.isNaN(now.x)||checker.isNaN(now.y)){
	 System.out.println("now.x = "+now.x+" now.y = "+now.y);
	 return 2;
       }
    }
    
        
    int backt=0;
    while(backt!=numberofpoint){
      if(numberofpoint<=11){
	return 1;
      }
      backt = numberofpoint;
       reparameterization();
       if(numberofpoint<=11){
	 return 1;
       }
    }
    if(numberofpoint>8){
      if(numberofpoint<=11)return 1;
      return 0;
    }else{
      return 1;
    }
  } 


 private void changeextreme(Vertex now){
   if(next(next(now))==Tail){
     if(now.k<next(next(Head)).k){
       now.extreme = 1;
     }else{
       next(next(Head)).extreme = 1;
     }
   }else{
     if(now.k<next(next(now)).k){
       now.extreme = 1;
     }else{
       next(next(now)).extreme = 1;
     }
   }
 
 } 
 public void reparameterization(){
    
    double dumx,dumy;
	Vertex dummy;
	Vertex now = Head;
	while(next(now)!=Tail){
	    now  = next(now);
	     if(next(now)==Tail)break;
	    if(Distance(next(now),now)<= (Low2/scale)&&next(now).extreme!=1){
	      
	      //if(next(now).extreme==1)changeextreme(now);
	      DeleteN(now);
	      numberofpoint--;
	      
	    }
	    if(next(now)==Tail)break;
	}
	if(next(now)==Tail){
	  if(Distance(now,next(Head))<= (Low2/scale)&&next(Head).extreme!=1){
	    //if(next(Head).extreme==1)changeextreme(now);
	    dummy = next(next(Head));
	    Head.next = dummy;
	    dummy.back = Head; 
	    numberofpoint--;
	  }
	}
	
  }
 
  public int Update222(){
    
    UpdateProperty();
    
    double dx,dy,speed,dummy;
    double epcilon=0.01;
    
    Vertex now = next(Head);
    
  //  settype(back(Tail),now,next(now));
    while(next(next(now))!=Tail){ 
      now = next(now);
    //  settype(back(now),now,next(now));
    }
    now = next(now);
    //settype(back(now),now,next(Head));
    //epcilon = ((mindis*mindis*mindis)/(5.0*numberofpoint));
    //epcilon = ((mindis*mindis)/(numberofpoint));
    
   epcilon = ((mindis)/(numberofpoint));
    now = Head;
    //System.out.println(" ");
    while(next(now)!=Tail){
      now = next(now);
      //dummy = now.k*now.k;
      speed = now.k;
      
      dx = now.x +epcilon*(speed*now.normal.x + G(now)*now.tangent.x);
      dy = now.y +epcilon*(speed*now.normal.y+ G(now)*now.tangent.y);
      //dx = now.x +epcilon*now.k*now.normal.x;
      //dy = now.y +epcilon*now.k*now.normal.y;
      now.x = dx;
      now.y = dy;
    }
    
    if(numberofpoint>3){
       eliminate();
       return 0;
    }else{
      return 1;
    }
    
  } 
  private double G(Vertex now)
    {	return ((now.dis2 - now.dis1)/(5.0*(now.dis2 + now.dis1)));
    }
  private void UpdateProperty(){
    Vertex now = next(Head);
    now.dis1 = Distance(now,back(Tail));
    mindis = now.dis1;
    now.dis2 = Distance(now,next(now));
    if(now.dis2<mindis)mindis = now.dis2;
    
    while(next(next(now))!=Tail){
      now = next(now);
      now.dis1 = back(now).dis2;
      now.dis2 = Distance(now,next(now));
      if(now.dis2<mindis)mindis = now.dis2;
    }
    now =  next(now);
    now.dis1 = back(now).dis2;
    now.dis2 = Distance(now,next(Head));
    if(now.dis2<mindis)mindis = now.dis2;
    
    now = next(Head);
    
    now.d1 = Round(back(Tail),now,next(now));
    now.d2 = Round2(back(Tail),now,next(now));
    now.tangent = getTangent(back(Tail),now,next(now));
    

    now.normal = getNormalAfterT(now);
    while(next(next(now))!=Tail){
      now = next(now);
      now.d1 = Round(back(now),now,next(now));
      now.d2 = Round2(back(now),now,next(now));
      now.tangent = getTangent(back(now),now,next(now));
      now.normal = getNormalAfterT(now);
    }
    
    now =  next(now);
    now.d1 = Round(back(now),now,next(Head));
    now.d2 = Round2(back(now),now,next(Head));
    now.tangent = getTangent(back(now),now,next(Head));
    now.normal = getNormalAfterT(now);


    now = Head;
    while(next(now)!=Tail){
      now = next(now);
      now.k = getK(now);
    }
    

    /* get kss 
    now = next(Head);
    now.kss = getKss(back(Tail),now,next(now));
    while(next(next(now))!=Tail){
      now = next(now);
      now.kss = getKss(back(now),now,next(now));
    }
    now = next(now);
    now.kss = getKss(back(now),now,next(Head));
    */
        
  }
  
  
    private void settype(Vertex backn,Vertex now,Vertex nextn){
    double dn1,dn2,dn3;
    dn1 = backn.k;
    dn2 = now.k;
    dn3 = nextn.k;
    if(dn2<0.0){
    if(dn2< dn3 && 
    dn2< dn1){
    now.extreme = 1;
    }else if(dn2> dn3 && 
    dn2> dn1){
    now.extreme = 3;
    }else{
    now.extreme = 0;
    }
    }else{
    if(dn2< dn3 && 
    dn2< dn1){
    now.extreme = 2;
    }else if(dn2> dn3 && 
    dn2> dn1){
    now.extreme = 4;
    }else{
    now.extreme = 0;
    }
    }
    }
  
  private void settypeChi(Vertex backn2,Vertex backn,Vertex now,
			  Vertex nextn,Vertex nextn2){
    double dn1,dn2,dn3,dn4,dn5,disave,d1;
    dn1 = backn2.k;
    dn2 = backn.k;
    dn3 = now.k;
    dn4 = nextn.k;
    dn5 = nextn2.k;
    disave = (backn2.dis2 + backn.dis2 + now.dis2 + nextn.dis2)/4.0;
    
    d1 = (-dn5+8.0*dn4-8.0*dn2+dn1)/(12.0*disave);
    /*
    // if((dn3<0.0)&&(dn2<dn1)&&(dn4<dn5)&&(dn3<dn2)&&(dn3<dn4)&&(Math.abs(d1)<0.000001)){
    */
    if(Math.abs(d1)<0.0001){
      
      now.extreme = 1;/* negative minimum */
    }else{
      now.extreme = 0;
    }
    
  }
  
  private DoubleVector getTangent(Vertex backn,Vertex now,Vertex nextn){
    DoubleVector d1 = NewNormalize(now.d1);
    if(d1.size!=0){
      return d1;
    }else{
      DoubleVector dtangent2;
      if(backn.x==0.0&&backn.y==0.0){
	dtangent2 = 
	  Normalize(new DoubleVector((-(now).x + (backn.x)),
				     (-(now).y + (backn.y))));
      }else{
	dtangent2 = 
	  Normalize(new DoubleVector(((now).x - (nextn.x)),
				     ((now).y - (nextn.y))));
	
      }
      return dtangent2;
    }
  }
  private DoubleVector getNormalAfterT(Vertex now){
     return new DoubleVector(-now.tangent.y,now.tangent.x);
  }
  private DoubleVector getNormal(Vertex backn,Vertex now,Vertex nextn){
    DoubleVector d1 = Normalize(now.d1);
    if(d1.size!=0){
      return new DoubleVector(-d1.y,d1.x);
    }else{
      DoubleVector dnormal2;
       if(backn.x==0.0&&backn.y==0.0){
	dnormal2 = 
	  Normalize(new DoubleVector((-(now).y + (backn.y)),
				     -(-(now).x + (backn.x))));
      }else{
	dnormal2 = 
	  Normalize(new DoubleVector(((now).y - (nextn.y)),
				     -((now).x - (nextn.x))));
      }
      return dnormal2;
    }
  }
   public double getKss(Vertex backn,Vertex now,Vertex nextn){
   double dkss;
   dkss = (2.0*nextn.k)/(now.dis2*(now.dis2 + now.dis1)) - 
     (2.0*now.k)/(now.dis1*now.dis2) + 
     (2.0*backn.k)/(now.dis1*(now.dis2 + now.dis1));
   return dkss;
  
  } 
public double getK(Vertex now){
  double curvature;
  double dd1x = (now.d1.x*now.d1.x);
  double dd1y = (now.d1.y*now.d1.y);
  double dx1y2 = (now.d1.x*now.d2.y);
  double dx2y1 = (now.d1.y*now.d2.x);
    if((dd1x==0.0)&&(dd1y==0.0)){
      curvature = 1000.0;
    }else{
      curvature = ((dx1y2 - dx2y1)/Math.pow(dd1x + dd1y,1.5));  
    }
    return curvature;
}
 private DoubleVector Round(Vertex backn,Vertex now,Vertex nextn){
   
    double dx,dy;
    dx = (((nextn.x - now.x)/now.dis2) + ((now.x - backn.x)/now.dis1) 
	  - ((nextn.x - backn.x)/(now.dis1+now.dis2))); 
    dy = (((nextn.y - now.y)/now.dis2) + ((now.y - backn.y)/now.dis1) 
	  - ((nextn.y - backn.y)/(now.dis1+now.dis2))); 
    return new DoubleVector(dx,dy);
 }
 private DoubleVector Round2(Vertex backn,Vertex now,Vertex nextn){
   double dx,dy;
   dx = (2.0*nextn.x)/(now.dis2*(now.dis2 + now.dis1)) - 
     (2.0*now.x)/(now.dis1*now.dis2) + 
     (2.0*backn.x)/(now.dis1*(now.dis2 + now.dis1));
   dy = (2.0*nextn.y)/(now.dis2*(now.dis2 + now.dis1)) - 
     (2.0*now.y)/(now.dis1*now.dis2) + 
     (2.0*backn.y)/(now.dis1*(now.dis2 + now.dis1));
   return new DoubleVector(dx,dy);
 }
 private DoubleVector NewNormalize(DoubleVector in)
    {
      DoubleVector v = new DoubleVector(in.x,in.y);
      v.size = Math.sqrt((v.x)*(v.x)+(v.y)*(v.y));
      if(v.size!=0){
	v.x = (double)(v.x/v.size);
	v.y = (double)(v.y/v.size);
	v.size = 1.0;
      }else{
        v.size = 0.0;
      }
      return v;
    }
 private DoubleVector Normalize(DoubleVector v)
    {
      v.size = Math.sqrt((v.x)*(v.x)+(v.y)*(v.y));
      if(v.size!=0){
	v.x = (double)(v.x/v.size);
	v.y = (double)(v.y/v.size);
	v.size = 1.0;
      }else{
        v.size = 0.0;
      }
      return v;
    }
 private void Init(Vertex h,Vertex t)
    {
      h.next = new Vertex();
      t.back = new Vertex();
      h.next = t;
      t.back = h;
    }
  private void DeleteN(Vertex now)
    {
      Vertex dummy1 = next(next(now));
      dummy1.back =now;
	now.next = dummy1;
    }
  private void Insert(Vertex now,Vertex after)
    {
      Vertex dummy1 = now.next;
      now.next = after;
      after.back = now;
      after.next = dummy1;
	dummy1.back = after;
    }
  
  private double Distance(Vertex p1,Vertex p2)
    {
      DoubleVector v1 = new DoubleVector(p1.x,p1.y);
	DoubleVector v2 = new DoubleVector(p2.x,p2.y);
	return Distance(v1,v2);
    }
  private double Distance(DoubleVector v1,DoubleVector v2)
  {
    DoubleVector v = new DoubleVector((v2.x-v1.x),(v2.y-v1.y));
    return ((double)(Math.sqrt((v.x*v.x)+(v.y*v.y))));
  }
  
  private Vertex next(Vertex now)
    {
      return (now.next);
    }
  private Vertex back(Vertex now)
    {
      return (now.back);
    }
  /*
  public void Append(DoubleVector dv,int ex,double dk)
    {
      Vertex now = new Vertex(dv.x,dv.y);
      now.extreme = ex;
      now.k = dk;
      Vertex dummy = Tail.back;
      now.next = Tail;
      Tail.back = now;
      now.back = dummy;
      dummy.next =now;
      numberofpoint++;
    }
  */
  public void Append(DoubleVector dv,int ex)
    {
      Vertex now = new Vertex(dv.x,dv.y);
      now.extreme = ex;
     
      Vertex dummy = Tail.back;
      now.next = Tail;
      Tail.back = now;
      now.back = dummy;
      dummy.next =now;
      numberofpoint++;
      firstnumofp++;
    }
  
  private double ScalarV(DoubleVector dv1,DoubleVector dv2){
    return (dv1.x*dv2.x + dv1.y*dv2.y);
  }

public void insert()
    {
	
	double dumx,dumy,dumk;
	Vertex now = Head;
	while(next(next(now))!=Tail){
	    now  = next(now);
	    if(Distance(next(now),now)>= (High/scale)){
		dumx = ((now.x + (now.next).x)/2.0);
		dumy = ((now.y + (now.next).y)/2.0);
		dumk = ((2.0*now.k*(now.next).k)/(now.k+(now.next).k));
		Vertex inpoint = new Vertex(dumx,dumy);
		inpoint.k = dumk;
		Insert(now,inpoint);
		numberofpoint++;
		now  = next(now);
	    }
	}
    }

  public DoubleVector getRoundLaplace(Vertex backn,Vertex now,Vertex nextn){
   
    double dx,dy;
    dx = (((nextn.mid.x - now.mid.x)/now.dis2) + ((now.mid.x - backn.mid.x)/now.dis1) 
	  - ((nextn.mid.x - backn.mid.x)/(now.dis1+now.dis2))); 
    dy = (((nextn.mid.y - now.mid.y)/now.dis2) + ((now.mid.y - backn.mid.y)/now.dis1) 
	  - ((nextn.mid.y - backn.mid.y)/(now.dis1+now.dis2))); 
    return new DoubleVector(dx,dy);
 }
  public DoubleVector getLaplace(Vertex backn,Vertex now,Vertex nextn){
    DoubleVector v1 = Normalize(new DoubleVector((-now.x + backn.x),
						 (-now.y + backn.y)));
    DoubleVector v2 = Normalize(new DoubleVector((-now.x + nextn.x),
						 (-now.y + nextn.y)));
    return new DoubleVector((v1.x+v2.x),(v1.y+v2.y));
  
  
  }
  private double VertexSize(Vertex dv){
   return Math.sqrt((dv.x*dv.x+dv.y*dv.y));
 }
  private double VectorSize(DoubleVector dv){
   return Math.sqrt((dv.x*dv.x+dv.y*dv.y));
 }


private void eliminate()
    {
	double dumx,dumy;
	Vertex dummy;


	Vertex now = next(Head);
	now.mid = new DoubleVector((back(Tail).x + next(now).x)/2.0,
				   (back(Tail).y + next(now).y)/2.0);
	      	
	while(next(next(now))!=Tail){
	    now  = next(now);
	    now.mid = new DoubleVector((back(now).x + next(now).x)/2.0,
				       (back(now).y + next(now).y)/2.0);
	}
	now  = next(now);
	now.mid = new DoubleVector((back(now).x + next(Head).x)/2.0,
				   (back(now).y + next(Head).y)/2.0);


	now = Head;
	
	while(next(now)!=Tail){
	    now  = next(now);
	    if(now.dis1<= (Low/scale)||(now.dis2<=(Low/scale))){
		now.x = now.mid.x;
		now.y = now.mid.y;
	      }
	}	
    }

private void eliminate222()
    {
	double dumx,dumy;
	Vertex dummy;
	Vertex now = Head;
	while(next(now)!=Tail){
	    now  = next(now);
	     if(next(now)==Tail)break;
	    if(Distance(next(now),now)<= (Low/scale)){
	      //DeleteN(now);
	      if(next(next(now))!=Tail){
		next(now).x = (now.x + next(next(now)).x)/2.0;
		next(now).y = (now.y + next(next(now)).y)/2.0;
	      }else{
		next(now).x = (now.x + next(Head).x)/2.0;
		next(now).y = (now.y + next(Head).y)/2.0;
	      } 
	      //numberofpoint--;
	    }
	    if(next(now)==Tail)break;
	}
	if(next(now)==Tail){
	  if(Distance(now,next(Head))<= (Low/scale)){
	    /*
	    dummy = next(Head);
	    Head.next = dummy;
	    dummy.back = Head; 
	     numberofpoint--;
	     */
	    next(Head).x = (now.x + next(next(Head)).x)/2.0;
	    next(Head).y = (now.y + next(next(Head)).y)/2.0;
	  }
	}

    }
}