class apskr{

// testavimui
static public final void main(String[] Arg){
 int[] a=arc(new double[]{10.0,0.0,10.0}, 20, 10+10*100,100);
 double[] d=rask(new int[]{20,14+700,7+700,0}, 4,100); my.print(d,"rask");
 d=raskIter(new int[]{(int)(10+20*Math.cos(1.0))+(int)(20*Math.sin(1.0))*100,
	(int)(10+20*Math.cos(1.2))+(int)(20*Math.sin(1.2))*100,
	(int)(10+20*Math.cos(1.4))+(int)(20*Math.sin(1.4))*100,
	(int)(10+20*Math.cos(1.6))+(int)(20*Math.sin(1.6))*100
	}, 4,100); my.print(d,"raskIter");

 double x_=6.0, y_=12.0, R=25.0, err,er2,q; 
 int n=100,w=200; int[] x=new int[n],xy=new int[n], y=new int[n];
 err=0.0;
 for (int i=0; i<n; i++){
	x[i]=(int)Math.round(x_+R*Math.cos(0.3+Math.PI/4*(i+0.5)/n));
 	y[i]=(int)Math.round(y_+R*Math.sin(0.3+Math.PI/4*(i+0.5)/n));
	q=Math.sqrt((x[i]-x_)*(x[i]-x_)+(y[i]-y_)*(y[i]-y_))-R;
	err+=q*q;
	xy[i]=x[i]+y[i]*w;
 }
 err/=n;
 my.print(x,"x"); my.print(y,"y");
// d=raskR(xy,n,w);
 d=raskR(x,y);
 er2=0.0;
 for (int i=0; i<n; i++){
	q=Math.sqrt((x[i]-d[0])*(x[i]-d[0])+(y[i]-d[1])*(y[i]-d[1]))-d[2];
	er2+=q*q;
 }
 er2/=n;
 my.print(new double[]{x_,y_,R,err,d[0],d[1],d[2],d[8],er2},"raskR:ox,oy,R,err");
 my.println(x[0]+" "+x[(n-1)/2]+" "+x[n-1]+" "+y[0]+" "+y[(n-1)/2]+" "+y[n-1]);
 d=tiese.fit(x,y); my.print(d,"c,s,x_,y_,err");
 double p=Math.sqrt((x[n-1]-x[0])*(x[n-1]-x[0])+(y[n-1]-y[0])*(y[n-1]-y[0]));
 my.print(new double[]{-(y[n-1]-y[0])/p,(x[n-1]-x[0])/p},"dd");
 raskIter(x,y);
// tikriname perTris
 int N=1 << 15;
 for (int i=0; i<99; i++){ perTris(
   new int[]{(int)(N*(Math.random()-0.5)),(int)(N*(Math.random()-0.5)),(int)(N*(Math.random()-0.5))},
   new int[]{(int)(N*(Math.random()-0.5)),(int)(N*(Math.random()-0.5)),(int)(N*(Math.random()-0.5))});
 perKeturis(
   new int[]{(int)(N*(Math.random()-0.5)),(int)(N*(Math.random()-0.5)),(int)(N*(Math.random()-0.5)),(int)(N*(Math.random()-0.5))},
   new int[]{(int)(N*(Math.random()-0.5)),(int)(N*(Math.random()-0.5)),(int)(N*(Math.random()-0.5)),(int)(N*(Math.random()-0.5))});
}
}
//

// megina (x_i,y_i) duomenis aproksimuoti apskritimo lanku
// Masyve grazina xo,yo,R,sigma_xo,sigma_yo,sigma_R
static public double[] raskIter(int[] xy, int n,int w){
 int N=xy.length; if (N<n) my.error("N>n");
 int[] x=new int[n], y=new int[n];
 for (int i=0; i<n; i++) {x[i]=xy[i]%w; y[i]=(xy[i]-x[i])/w;}
 return raskIter(x,y);
}

// grazina {ox,oy,R,c,s,x_,y_,r2};
static public double[] raskR(int[] xy, int n,int w){
 int N=xy.length; if (N<n) my.error("N>n");
 int[] x=new int[n], y=new int[n];
 for (int i=0; i<n; i++) {x[i]=xy[i]%w; y[i]=(xy[i]-x[i])/w;}
 return raskR(x,y);
}

static public double[] rask(int[] xy, int n,int w){
 int N=xy.length; if (N<n) my.error("N>n");
 int[] x=new int[n], y=new int[n];
 for (int i=0; i<n; i++) {x[i]=xy[i]%w; y[i]=(xy[i]-x[i])/w;}
 return rask(x,y);
}

static public double[] raskIter(int[] x, int[] y){

// Pradines reiksmes randame su raskR
// grazina {ox,oy,R,c,s,x_,y_,r2,err};
 double[] A=raskR(x,y);
 
 double x_=A[5],y_=A[6],a=A[0],a1=0,b=A[1],b1=0,
	r_=0.0,rm=r_,rr_,rx_,ry_,ep=1.0,tiksl=0.0000125,p,xi,yi,d,d1,d2;
 int n=x.length,it=0,maxit=10;
 d=1; d1=1/my.eps; d2=d1/2;
 while ((d>tiksl)&(it<maxit)&(d2<d1)){
	d1=d2;
	r_=0.0;rr_=0.0;rx_=0.0;ry_=0.0;
	for (int i=0; i<n; i++){
		xi=a-x[i];yi=b-y[i];
		p=Math.sqrt(xi*xi+yi*yi); if (p<my.eps) p=my.eps;
		r_+=p;rr_+=p*p;rx_+=xi/p;ry_+=yi/p;
	}
	r_/=n;rr_/=n;rx_/=n;ry_/=n;
	d2=rr_-r_*r_;
	a1=x_+r_*rx_; b1=y_+r_*ry_; 
	d=Math.abs(a1-a)+Math.abs(b1-b);
	if (d2<d1) {a=a1; b=b1;rm=r_;}
	it++;
//	my.print(new double[]{d,(double)it},"d,it");
 }
// my.print(new double[]{A[0],A[1],A[2],A[8],a,b,rm,d2,d1},"ox,oy,r_,err");
 return new double[]{a,b,rm,d,d1,d2};
}//raskIter

// grazina {ox,oy,R,c,s,x_,y_,r2};
static public double[] raskR(int[] x, int[] y){ 
 double[] d=tiese.fit(x,y);
// randame taskus (x_i,y_i) aproksimuojancia tiese
 double c=d[0],s=d[1],x_=d[2],y_=d[3];
 int n = x.length,maxit=10,it=0,N;
/* perrinkimo budu ieskomas minimumas
// atsisakiau, nes daug skaiciavimu
 N=0; for (int i=0; i<n-1; i++) N+=Math.abs(x[i+1]-x[i])+Math.abs(y[i+1]-y[i]);
 N=Math.max(30,N); N=(N/3)*3;
 double r1=0.0,rr_=0.0,r2=r1,d_=1/my.eps,
	R_0=Math.sqrt((x[n-1]-x[0])*(x[n-1]-x[0])+(y[n-1]-y[0])*(y[n-1]-y[0]))/2;
 double a,b,r_=0.0,ep=1.0,tiksl=0.0000125,p,w,xi,yi,dist=2*tiksl;
 for (int k=-N; k<=N; k++) if (Math.abs(k)>R_0) { 
	r_=0.0; rr_=0.0; a=x_+k*c;b=y_+k*s;
	for (int i=0; i<n; i++){
		p=Math.sqrt((x[i]-a)*(x[i]-a)+(y[i]-b)*(y[i]-b));
		r_+=p; rr_+=p*p;
	}
	p=rr_/n-(r_/n)*(r_/n);
	if (d_>p) {r1=k; d_=p;}
 }
*/

// surandame labiausiai nutolusius taskus
 int x0=x[0],x1=x[n-1],y0=y[0],y1=y[n-1],im=(n-1)/2;
 double  xv=(x0+x1)/2.0, yv=(y0+y1)/2.0,
	p0=c*(x0-xv)+s*(y0-yv),p1=c*(x1-xv)+s*(y1-yv), Rmax=-1.0,pp;
 for (int i=1; i<n-1; i++){
  pp=c*(x[i]-xv)+s*(y[i]-yv); pp=Math.max(Math.abs(pp-p0),Math.abs(pp-p1));
  if (Rmax<pp) {Rmax=pp; im=i;}
 }
// my.print(x,"x"); my.print(y,"y");
 double[] or=perTris(new int[]{x0,x[im],x1}, new int[]{y0,y[im],y1});
 double r1=0.0,rr_=0.0,r2=r1,d_=1/my.eps,
	R_0=Math.sqrt((x[n-1]-x[0])*(x[n-1]-x[0])+(y[n-1]-y[0])*(y[n-1]-y[0]))/2;
 double a,b,r_=0.0,ep=1.0,tiksl=0.0000125,p,w,xi,yi,dist=2*tiksl;

// kad (c,s) butu nukreiptas i vidu
 if (((or[0]-x_)*c+(or[1]-y_)*s)>0) {c=-c; s=-s;}

 r1=(or[0]-x_)*c+(or[1]-y_)*s;
 a=x_+r1*c;b=y_+r1*s;
 my.println("raskR: init "+or[0]+" "+or[1]+" "+a+" "+b+" "+or[2]+" ox,oy,a,b,r");

 p=-1;
 while ((dist>tiksl)&(it<maxit)&(p<d_)){
	if (p>=0) d_=p;
	r_=0.0;rr_=0.0;w=0.0; a=x_+r1*c;b=y_+r1*s;
	for (int i=0; i<n; i++){
		xi=a-x[i];yi=b-y[i];
		p=Math.sqrt(xi*xi+yi*yi); if (p<my.eps) p=my.eps;
		r_+=p;rr_+=p*p;w+=(xi*c+yi*s)/p;
	}
	r_/=n;w/=n;rr_/=n;
	p=rr_-r_*r_;
	r2=r_*w;
	dist=Math.abs(r2-r1); r1=r2;
	if (p>=d_) r2=r1;
	it++;
//	System.out.println(dist+" "+r_+" "+r2+" "+p+" d,r_,r2,err");
//	my.print(new double[]{dist,r_,(double)it},"d,r_,it");
 }
// my.print(new double[]{c,s,x_,y_,d_},"c,s,x_,y_,d_");
 return new double[]{x_+c*r2,y_+s*r2,r_,c,s,x_,y_,r2,d_};
}//raskIter

static public double[] rask(int[] x, int[] y){
 double[] A=null;
 int n = x.length;
 if (n!=y.length) my.error("x ir y skirtingu ilgiu: "+n+" "+y.length);
 if (n<3) return A;
//n>3
 final int N3=3;
 double[] a=new double[N3];
 A=new double[2*N3];
 int N=0,k=1,k2=k*2;
 my.print(n-k2,"n-k2");
 while (k2<n){
   for (int i=0; i<n-k2; i++){
	a=perTris(new int[]{x[i],x[i+k],x[i+k2]},new int[]{y[i],y[i+k],y[i+k2]});
	if (a!=null) {
//		my.print(a,"aa");
		for (int j=0; j<N3; j++){A[j]+=a[j]; A[j+N3]+=a[j]*a[j];}
		N++;
	}
   }
   k=k2; k2*=2;
 }
 if (N<1) return null;
 for (int j=0; j<N3; j++){A[j]/=N; A[j+N3]=Math.sqrt((A[j+N3]/N-A[j]*A[j])/N);}
 my.print(x,"x"); my.print(y,"y"); my.print(A,"A");
 return A;
}//rask

// Masyve grazina xo,yo,R
static public double[] perTris(int[] x, int[] y){
 double tiksl=1.0/Math.sqrt(1001); // tokio tikslumo pilnai pakanka, nes x,y sveiki
 double[] a=null;
 boolean perTiese;
 int n = x.length;
 if (n!=y.length) my.error("x ir y skirtingu ilgiu: "+n+" "+y.length);
 if (n!=3) my.error("x y ilgis != 3: "+n);
 double[] xv=new double[]{(x[0]+x[1])/2.0,(x[1]+x[2])/2.0},
	 yv=new double[]{(y[0]+y[1])/2.0,(y[1]+y[2])/2.0},
 	o;
 double xep=tiksl,yep=tiksl*Math.sqrt(2.0);
// my.print(x,"x"); my.print(y,"y");
 o=tiese.kirtim(new double[]{xv[0],xv[0]-(y[1]-y[0])},new double[]{yv[0],yv[0]+(x[1]-x[0])},
		new double[]{xv[1],xv[1]-(y[2]-y[1])},new double[]{yv[1],yv[1]+(x[2]-x[1])});
// pakartotinai su dirbtimnai pakeisti y
 perTiese=o==null;
 if (perTiese) o=tiese.kirtim(new double[]{xv[0]+xep,xv[0]+xep-(y[1]-y[0]-2*yep)},new double[]{yv[0]+yep,yv[0]+yep+(x[1]-x[0]-2*xep)},
		new double[]{xv[1],xv[1]-(y[2]-y[1])},new double[]{yv[1],yv[1]+(x[2]-x[1])});
 if (o==null) my.error("Ir pakartotinai d==null x="+my.toString(x)+", y="+my.toString(y));
 double R2=(o[0]-x[1])*(o[0]-x[1])+(o[1]-y[1])*(o[1]-y[1]);
 if (!perTiese){
	double p=Math.max(Math.abs(R2-((o[0]-x[0])*(o[0]-x[0])+(o[1]-y[0])*(o[1]-y[0]))),
			Math.abs(R2-((o[0]-x[2])*(o[0]-x[2])+(o[1]-y[2])*(o[1]-y[2]))));
	if (p>tiksl) my.warning("perTris: nepasiektas tikslumas:"+p+" R="+Math.sqrt(R2));
 }
 return new double[]{o[0],o[1],Math.sqrt(R2)};
}

// Masyve grazina xo,yo,r,R
static public double[] perKeturis(int[] x, int[] y){
 double tiksl=1.0/Math.sqrt(1001); // tokio tikslumo pilnai pakanka, nes x,y sveiki
 double[] a=null; double r,R;
 int n = x.length; if (n!=y.length) my.error("x ir y skirtingu ilgiu: "+n+" "+y.length);
 if (n!=4) my.error("x y ilgis != 4: "+n);
 double[] xv=new double[]{(x[0]+x[1])/2.0,(x[2]+x[3])/2.0},
	 yv=new double[]{(y[0]+y[1])/2.0,(y[2]+y[3])/2.0},
 	o;
 double xep=tiksl,yep=tiksl*Math.sqrt(2.0);
// my.print(x,"x"); my.print(y,"y");
 o=tiese.kirtim(new double[]{xv[0],xv[0]-(y[1]-y[0])},new double[]{yv[0],yv[0]+(x[1]-x[0])},
		new double[]{xv[1],xv[1]-(y[3]-y[2])},new double[]{yv[1],yv[1]+(x[3]-x[2])});
// pakartotinai su dirbtinai pakeisti y
 if (o==null) tiese.kirtim(new double[]{xv[0]+xep,xv[0]+xep-(y[1]-y[0]-2*yep)},new double[]{yv[0]+yep,yv[0]+yep+(x[1]-x[0]-2*xep)},
		new double[]{xv[1],xv[1]-(y[3]-y[2])},new double[]{yv[1],yv[1]+(x[3]-x[2])});
 R=Math.sqrt((o[0]-x[1])*(o[0]-x[1])+(o[1]-y[1])*(o[1]-y[1]));
 r=Math.sqrt((o[0]-x[3])*(o[0]-x[3])+(o[1]-y[3])*(o[1]-y[3]));
 double p;
 p=Math.max(Math.abs(R*R-((o[0]-x[0])*(o[0]-x[0])+(o[1]-y[0])*(o[1]-y[0]))),
		Math.abs(r*r-((o[0]-x[2])*(o[0]-x[2])+(o[1]-y[2])*(o[1]-y[2]))));
 if (p>tiksl) my.warning("perKeturis: nepasiektas tikslumas:"+p+", R="+R+", r="+r+my.toString(x)+my.toString(y));
 return new double[]{o[0],o[1],Math.min(r,R),Math.max(r,R)};
}

// Grazina lanka, o=(xo,yo,R,...toliau bet kas )
static public int[] arc(double[] o, int a, int b, int w){
 if (o.length<3) my.error("o.length<3: "+o.length);
 double R=o[2],f1,f2;
 int i0=a%w,j0=(a-i0)/w,i1=b%w,j1=(b-i1)/w;
 f1=Math.atan2(j0-o[1],i0-o[0]);
 f2=Math.atan2(j1-o[1],i1-o[0]);
 if (f2-f1>Math.PI) f2-=2*Math.PI; else if (f2-f1<=-Math.PI) f2+=2*Math.PI;
 int L=(int)(2*Math.sqrt((i1-i0)*(i1-i0)+(j1-j0)*(j1-j0)))+1,j;
 int[] c=new int[1*(L+1)];
 double h=(f2-f1)/L;
 for (int i=0; i<=L; i++){
	j=(int)(Math.round(o[0]+R*Math.cos(f1+i*h))+Math.round(o[1]+R*Math.sin(f1+i*h))*w);
//	c[4*i]=j-1;c[4*i+1]=j+1;c[4*i+2]=j+w;c[4*i+3]=j-w;
	c[i]=j;
 }
// my.print(c,"c");
 return c; 
}
}