import java.util.Vector;
class krastas {

static int N=0; //tasku skaicius
static int[] x=null,y=null;
static int[] x2=null,y2=null; //x2=2*x;y2=2*y; - naudinga skaiciavimu greitumui
		// ir pasilikti sveikoje aritmetikoje
static Vector V; // galimu krastiniu vektorius

static int NGK=0; // Galimu krastu skaicius
static int[] indAGK=null,indBGK=null;

static int NVV=0; // Trikampiu kuriuose visi (x[i],y[i]) tashkai yra viduje skaicius
static public double[] oxVV=null, oyVV=null, RVV=null;
static int NVI=0; // Trikampiu kuriuose visi (x[i],y[i]) tashkai yra isoreje skaicius
static public double[] oxVI=null, oyVI=null, RVI=null;

static final double bigR=9999.0;
static private double OX=0.0,OY=0.0,R=0.0;
static double dist,OXa,OYa,Ra; // geriausiai minmax-o metrikoje taskus aproksimuojantis apskritimas

static boolean toMatlab=false;
// testavimui
static public final void main(String[] Arg){
 double RR=Double.NaN; boolean bo=Double.isNaN(RR);
// my.println(""+bo);
 double x_=6.0, y_=2.0, R=35.0, err,er2,erm,q; 
 int N,n=10,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;
 System.out.println("clf; plot(x,y,'+'); axis equal; hold on;");
 double[] kr=raskR2(x,y);
 er2=0.0; erm=0.0;
 double ox=krastas.OXa, oy=krastas.OYa, Ra=krastas.Ra, r1=Ra-dist/2,r2=Ra+dist/2;
 for (int i=0; i<n; i++){
	q=Math.abs(Math.sqrt((x[i]-ox)*(x[i]-ox)+(y[i]-oy)*(y[i]-oy))-Ra);
	er2+=q*q; if (erm<q) erm=q;
 }
 er2/=n;
 my.print(new double[]{x_,y_,R,err,ox,oy,Ra,er2,krastas.dist,erm*2},"krastas:ox,oy,R,err,erm");
 System.out.println("x=["+my.toString(x)+"];");
 System.out.println("y=["+my.toString(y)+"];");
 System.out.println("t=0.3:0.01:0.3+3.14/4;");
 System.out.println("plot("+x_+"+"+R+"*cos(t),"+y_+"+"+R+"*sin(t));");
 System.out.println("plot("+ox+"+"+r1+"*cos(t),"+oy+"+"+r1+"*sin(t),'g');");
 System.out.println("plot("+ox+"+"+r2+"*cos(t),"+oy+"+"+r2+"*sin(t),'g');");
 System.out.println("plot("+ox+"+"+Ra+"*cos(t),"+oy+"+"+Ra+"*sin(t),'r');");
}
//

static public double[] raskR2(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 raskR2(x,y);
}

public static double raskR(int[] X,int[] Y){
/* ishmetame vienodus
 int NX=X.length, DX=my.max(X)-my.min(X)+1;
 int[] xx=new int[NX],XY=new int[NX], ix;
 for (int j=0; j<NX; j++) xx[j]=X[j]+Y[j]*DX;
 ix=my.sort(xx); N=1;
*/
 N=X.length;
 x=new int[N];y=new int[N];x2=new int[N]; y2=new int[N];
 for (int j=0; j<N; j++) {x[j]=X[j];y[j]=Y[j]; x2[j]=2*x[j];y2[j]=2*y[j];}
 indAGK=new int[N*(N-1)/2]; indBGK=new int[N*(N-1)/2];
 for (int j=0; j<N; j++) for (int i=j+1; i<N; i++)
  if (galimasKrastas(X[j],Y[j],X[i],Y[i])) {
//	System.out.println("plot(["+X[j]+" "+X[i]+"],["+Y[j]+" "+Y[i]+"],'g');");
	indAGK[NGK]=j;indBGK[NGK]=i; NGK++;
 }
 int A,B,C,D;
 double a; dist=1/my.eps;
 for (int j=0; j<NGK; j++){
	A=indAGK[j];B=indBGK[j];
	for (int i1=0; i1<N; i1++) for (int i2=i1+1; i2<N; i2++)	
		if ((i1!=A)|(i2!=B)) {	C=i1;D=i2;
//	for (int i=j+1; i<NGK; i++) {	C=indAGK[i];D=indBGK[i];
		a=atstumasTarpAtkarpu(X[A],Y[A],X[B],Y[B],X[C],Y[C],X[D],Y[D]);
//		my.println(""+krastas.OX);
		if (Double.isNaN(krastas.OX)){
			my.println("? "+my.toString(new int[]{X[A],Y[A],X[B],Y[B],X[C],Y[C],X[D],Y[D]}));
		}

		if (!Double.isNaN(a)) if (dist>Math.abs(a))
			{OXa=OX;OYa=OY;Ra=R;dist=Math.abs(a);}
	}
 }
 return dist;
}

// kitas raskR variantas
public static double[] raskR2(int[] X,int[] Y){
 N=X.length;
 x=new int[N];y=new int[N];x2=new int[N]; y2=new int[N];
 for (int j=0; j<N; j++) {x[j]=X[j];y[j]=Y[j]; x2[j]=2*x[j];y2[j]=2*y[j];}
 galimiKrastai(); NGK=V.size(); my.println(my.toString(new int[]{N,NGK}));
 int A,B,C,D; int[] w;
 double a; dist=1/my.eps;
 for (int j=0; j<NGK; j++){	w=(int[]) V.get(j); A=w[0];B=w[1];
// for (int j=0; j<N; j++){ A=j
	for (int i1=0; i1<N; i1++) for (int i2=i1+1; i2<N; i2++)	
		if ((i1!=A)|(i2!=B)) {	C=i1;D=i2;
//	for (int i=j+1; i<NGK; i++) {	w=(int[]) V.get(i); C=w[0];D=w[1];
		a=atstumasTarpAtkarpu(X[A],Y[A],X[B],Y[B],X[C],Y[C],X[D],Y[D]);
//		my.println(""+krastas.OX);
		if (Double.isNaN(krastas.OX)){
			my.println("? "+my.toString(new int[]{X[A],Y[A],X[B],Y[B],X[C],Y[C],X[D],Y[D]}));
		}

		if (!Double.isNaN(a)) if (dist>Math.abs(a))
			{OXa=OX;OYa=OY;Ra=R;dist=Math.abs(a);}
	}
 }
 return new double[]{OXa,OYa,Ra,dist};
}

public static double raskRfast(int[] X,int[] Y){
 N=X.length; int N2=(N+1)/2; double[] t1,t2,o,d;
 x=new int[N];y=new int[N];x2=new int[N]; y2=new int[N];
 for (int j=0; j<N; j++) {x[j]=X[j];y[j]=Y[j]; x2[j]=2*x[j];y2[j]=2*y[j];}

// per kaires ir desines puses tasku pravedame minimizuojancias tieses
// ir randame centra
 t1=tiese.fit(my.move(X,0,N2),my.move(Y,0,N2));
 t2=tiese.fit(my.move(X,N2-1,N),my.move(Y,N2-1,N));
 o=tiese.kirtim(new double[]{t1[2],t1[2]+t1[0]},new double[]{t1[3],t1[3]+t1[1]},
		new double[]{t2[2],t2[2]+t2[0]},new double[]{t2[3],t2[3]+t2[1]});
 if (o==null)  o=tiese.kirtim(new double[]{t1[2],t1[2]+t1[0]+0.01},new double[]{t1[3],t1[3]+t1[1]},
		new double[]{t2[2],t2[2]+t2[0]-0.01},new double[]{t2[3],t2[3]+t2[1]});
 int NN=N*N; d=new double[NN];
 for (int j=0; j<N; j++) for (int i=0; i<N; i++)
   if (i<=j+1) d[i+N*j]=1/my.eps; else d[i+N*j]=
	Math.abs(tiese.atstumas2t(new double[]{X[j],X[i]},new double[]{Y[j],Y[i]},o[0],o[1]));
 int[] ind=my.sort(d);
 my.print(new double[]{d[ind[0]],d[ind[1]],d[ind[2]],d[ind[3]],d[ind[4]],d[ind[5]]},"d");

// Ytraukiame perrinkimui tik perspektyviausias krastines
 NGK=Math.min(N,Math.max(4,N/4));
 int A,B,C,D;
 double a; dist=1/my.eps;
 for (int j=0; j<NGK; j++){
	A=ind[j]%N;B=(ind[j]-A)/N;
	for (int i=j+1; i<NGK; i++){
		C=ind[i]%N;D=(ind[i]-C)/N;
		System.out.println("plot(["+X[A]+" "+X[B]+"],["+Y[A]+" "+Y[B]+"],'g');");
		a=atstumasTarpAtkarpu(X[A],Y[A],X[B],Y[B],X[C],Y[C],X[D],Y[D]);
		if (!Double.isNaN(a)) if (dist>Math.abs(a))
			{OXa=OX;OYa=OY;Ra=R;dist=Math.abs(a);}
	}
 }
 return dist;
}

static public boolean galimasKrastas(int x0, int y0, int x1, int y1){
 int dx=x1-x0,dy=y1-y0;
 int xv2=x1+x0, yv2=y1+y0, R2_4=dx*dx+dy*dy,wx,wy;

 // pradzioje ziurime ar gali buti visi isoreje
 int i=0;
 while (i<N){
	if ((x[i]-x0)*dy<(y[i]-y0)*dx) // jei taskas kitoje puseje -
				// tikrinsime ar jis gali papulti i skrituly
	 if (((x2[i]-xv2)*(x2[i]-xv2)+(y2[i]-yv2)*(y2[i]-yv2))>R2_4) break;
	i++;
 }
 if (i==N)  return true; // gali atsirasti apskritimas einantis per atkarpos taskus,
			// kad visi taskai butu vienoje puseje

 // meginame i kita puse
 i=0;
 while (i<N){
	if ((x[i]-x0)*dy>(y[i]-y0)*dx) // jei taskas kitoje puseje -
				// tikrinsime ar jis gali papulti i skrituly
	 if (((x2[i]-xv2)*(x2[i]-xv2)+(y2[i]-yv2)*(y2[i]-yv2))>R2_4) break;
	i++;
 }
 if (i==N)  return true; // gali atsirasti apskritimas einantis per atkarpos taskus,
			// kad visi taskai butu vienoje puseje

 return false; 
}

static public void galimiKrastai(){
 boolean galimas;
 double[] d;
 double ox,oy,R2,dx,dy;
 String S;
 int i,x0,x1,x2,y0,y1,y2,idx,idy,K=0;
 V=new Vector();
 for (int ii=0; ii<N; ii++) for (int jj=0; jj<N; jj++) 
   if (jj!=ii) for (int kk=ii+1; kk<N; kk++) if (kk!=jj) {
    K++;
    x0=x[ii];x1=x[jj];x2=x[kk];y0=y[ii];y1=y[jj];y2=y[kk];
    d=apskr.perTris(new int[]{x0,x1,x2},new int[]{y0,y1,y2});
    if (d==null){ // vienoje tieseje
	S="r";
 	idx=x1-x0; idy=y1-y0;
	i=0; while (i<N) if ((x[i]-x0)*idy!=(y[i]-y0)*idx) break; else i++;
//	S+=i;
	if (i!=N){ //tikriname ar like toje pacioje puseje
	   int is=(x[i]-x0)*idy-(y[i]-y0)*idx; i++;
	   while (i<N) if (((x[i]-x0)*idy-(y[i]-y0)*idx)*is<0) break; else i++;
	}
//	S+=i;
    }
	else // ne vienoje tieseje
    {
	S="g";
	ox=d[0];oy=d[1];R2=d[2]*d[2]; 
	// pradzioje ziurime visi isoreje
	i=0; while (i<N){ dx=x[i]-ox;dy=y[i]-oy; if (dx*dx+dy*dy<R2) {//S+=+i+"B"; 
									break;} 
//		S+=+i+"C";
		 i++;}
//	S+=i+",ox="+ox+",oy="+oy+",R2="+R2;
	if (i!=N){ // nepasiseke, teks tikrinti gal visi viduje
		i=0; while (i<N){dx=x[i]-ox;dy=y[i]-oy; if (dx*dx+dy*dy>R2) break;else i++;}
		S="b";
//		S+=i;
	}
    }
//	S+=i;
//	my.println(S);
    if (i==N) {// papildome galimu krastu vektoriu
//	System.out.println("plot(["+x[ii]+" "+x[jj]+"],["+y[ii]+" "+y[jj]+"],'--"+S+"');");
//	System.out.println("plot(["+x[kk]+" "+x[jj]+"],["+y[kk]+" "+y[jj]+"],'--"+S+"');");
	V.add(new int[]{ii,jj}); V.add(new int[]{jj,kk});
    }
 }
 my.println("K="+K);
} //galimiKrastai()


// grazina 1, jei visi (x[i],y[i]) yra skritulio isoreje
// grazina 2, jei visi (x[i],y[i]) yra skritulio viduje
// grazina 3, jei visi (x[i],y[i]) yra apskritime
// grazina 0, kitais atvejais

static public double atstumasTarpAtkarpu(int Ax,int Ay,int Bx,int By,int Cx,int Cy,int Dx,int Dy){ 
// R=Double.NaN; OX=Double.NaN; OY=Double.NaN;
 int i,p;
 int ABx=Bx-Ax, ABy=By-Ay, CDx=Dx-Cx, CDy=Dy-Cy;
 boolean lygiagrecios=(ABx*CDy==CDx*ABy);
 if (lygiagrecios){
   double AB=Math.sqrt(ABx*ABx+ABy*ABy),c=-ABy/AB,s=ABx/AB,
	 ats=Math.abs(ABy*(Cx-Ax)-ABx*(Cy-Ay))/AB;
   OX=Ax+ats*c*bigR;OY=Ay+ats*s*bigR; R=bigR+ats/2;
   if (ABy*(Cx-Ax)==ABx*(Cy-Ay)){ // vienoje tieseje
	i=0;
	while (i<N) if (ABy*(x[i]-Ax)!=ABx*(y[i]-Ay)) break; else i++;
	if (i==N) return 0.0; // visi taskai toje pacioje tieseje
		else return Double.NaN;
   }
      else{ // dviejose lygiagreciose tiesese
	if ((ABx*CDx+ABy*CDy)>0) { //sukeiciame C ir D tasku vietomis, kad kampas tarp atkarpu butu bukas
		p=Dx;Dx=Cx;Cx=p; p=Dy;Dy=Cy;Cy=p; CDx=-CDx;CDy=-CDy;}
	i=0;
	while (i<N) if ((ABy*(x[i]-Ax)-ABx*(y[i]-Ay))*(CDy*(x[i]-Cx)-CDx*(y[i]-Cy))<0) break; else i++;
//	graziname atstuma tarp lygiagreciu tiesiu arba NaN
	if (i==N) return ats;
		else return Double.NaN;
   }
 }
   else{ //nelygiagrecios
	boolean C_=(((Ax==Cx)&(Ay==Cy))|((Bx==Cx)&(By==Cy))),
		D_=(((Ax==Dx)&(Ay==Dy))|((Bx==Dx)&(By==Dy))),
		sudaroApskr=C_|D_;
	double[] d=apskr.perKeturis(new int[]{Ax,Bx,Cx,Dx},new int[]{Ay,By,Cy,Dy});
	OX=d[0];OY=d[1];R=(d[2]+d[3])/2;
	if (Double.isNaN(OX)) my.error(my.toString(new int[]{Ax,Bx,Cx,Dx})+
		my.toString(new int[]{Ay,By,Cy,Dy}));
	if (R==Double.NaN) my.error("Su !|| R==Double.NaN");
	if (sudaroApskr) return atstumasIkiApskritimo(OX,OY,R);
		else return atstumasIkiZiedo(OX,OY,d[2]*d[2],d[3]*d[3]);
   } 

} //atstumasTarpAtkarpu

// grazina:
// teigiama atstuma jei visi (x[i],y[i]) yra skritulio isoreje
// neigiama atstuma, jei visi (x[i],y[i]) yra skritulio viduje
// NaN kitais atvejais
static public double atstumasIkiApskritimo(double ox, double oy, double R2){
 double d=R2,p;
 int i=0; while (i<N){
	d=(x[i]-ox)*(x[i]-ox)+(y[i]-oy)*(y[i]-oy);
	if ((d>R2)|(d<R2)) break;
	i++;
 }
 if (i==N) return 0.0; // visi yra apskritime
 i++;
 if (d>R2){ // taskai isoreje
 	while (i<N){
		p=(x[i]-ox)*(x[i]-ox)+(y[i]-oy)*(y[i]-oy);
		if (p<R2) break; if (d<p) d=p;
		i++;
	}
	if (i==N) return (d-R2)/(Math.sqrt(d)+Math.sqrt(R2)); // visi yra isoreje
		else return Double.NaN;
 }
	else {//tikriname ar visi like viduje
 	while (i<N){
		p=(x[i]-ox)*(x[i]-ox)+(y[i]-oy)*(y[i]-oy);
		if (p>R2) break; if (d>p) d=p;
		i++;
	}
	if (i==N) return -(R2-d)/(Math.sqrt(d)+Math.sqrt(R2)); // visi yra viduje
		else return Double.NaN;
 }
} //atstumasIkiApskritimo

static public double atstumasIkiZiedo(double ox, double oy, double r2, double R2){
 if (r2>R2) {double dummy=R2; R2=r2; r2=dummy;}
 double d;
 int i=0; while (i<N){
	d=(x[i]-ox)*(x[i]-ox)+(y[i]-oy)*(y[i]-oy);
	if ((d>R2)|(d<r2)) break;
	i++;
 }
 if (i==N) return (R2-r2)/(Math.sqrt(R2)+Math.sqrt(r2)); // visi taskai ziede
 return Double.NaN;
} //atstumasIkiZiedo

  public String toString() { return "\tN="+N+",\tNGK="+",\tNVV="+NVV+",\tNVI"+NVI;}
}