using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

// using System.Numerics;
using System.Runtime.CompilerServices;
using System.Diagnostics;
using ll=System.Int64;
using static Contest_F.MyIO;



public class Contest_F
{
	static void swap1<T>(ref T a, ref T b) { T t = a; a = b; b = t; }
	static void swap2<T>(ref T a, ref T b) where T : IComparable { if (a.CompareTo(b)==1) swap1(ref a, ref b); }  // b の方が小さければ交換
	static bool chmin<T>(ref T a, T b) where T : IComparable { if (a.CompareTo(b)== 1) { a = b; return true; } return false; }  // b の方が小さければ a を更新
	static bool chmax<T>(ref T a, T b) where T : IComparable { if (a.CompareTo(b)==-1) { a = b; return true; } return false; }  // b の方が大きければ a を更新
	static bool inside(long i, long n) => (0<=i&&i<n);
	static bool inside(long x, long y, long w, long h) => (inside(x,w)&&inside(y,h));
	static T min<T>(params T[] a) where T : IComparable => a.Min();
	static T max<T>(params T[] a) where T : IComparable => a.Max();
	static long mod(long a, long m) { var v = a%m; return (v<0?v+m:v); }
	static T[][] init<T>(long len1,long len2,T val) where T : struct { T[][] m = new T[len1][]; for (int i=0;i<m.Length;i++) m[i] = Enumerable.Repeat(val,(int)len2).ToArray(); return m; }
	static T[][][] init<T>(long len1,long len2,long len3,T val) where T : struct { T[][][] m = new T[len1][][]; for (int i=0;i<m.Length;i++) m[i] = init(len2,len3,val); return m; }
	public const long MOD1 = 1000000007; // 10^9+7
	public const double EPS1 = 1e-8;
	public const long INF1 = 1000000000000000;  // 10^15

	public static void Main() {
		checked{
			long  n;
			MyIO.RM(out n);
			VT<double,double>[] xyl;
			RL(n,out xyl);

			Point[] ps = new Point[n];
			for (int i = 0; i < n; i++)
			{
				ps[i] = new Point(xyl[i].Item1,xyl[i].Item2);
			}

			var ans = MyGeom2.Minball( MyGeom2.ConvexHull( ps)).R;

			WM(ans);
		}
	}














#region MyIO

public struct VT<T,U>
{
	public T Item1; public U Item2;
    public VT(T a,U b) { Item1 = a; Item2 = b; }
}
public struct VT<T,U,V>
{
	public T Item1; public U Item2; public V Item3;
    public VT(T a,U b,V c) { Item1 = a; Item2 = b; Item3 = c; }
}
public struct VT<T,U,V,W>
{
	public T Item1; public U Item2; public V Item3; public W Item4;
    public VT(T a,U b,V c,W d) { Item1 = a; Item2 = b; Item3 = c; Item4 = d; }
}

public static class MyIO
{
	class Prt : System.IO.StreamWriter
	{
		public override IFormatProvider FormatProvider { get { return System.Globalization.CultureInfo.InvariantCulture; } }
		public Prt(System.IO.Stream s) : base(s,new UTF8Encoding(false,true)) {}
		public Prt(System.IO.Stream s,Encoding e) : base(s,e) {}
	}
	
	static char[] sp = new char[] {' '};
	[MethodImpl(256)]
	static bool eq<T,U>() => typeof(T).Equals(typeof(U));
	[MethodImpl(256)]
	static T ct<T,U>(U a) => (T)Convert.ChangeType(a,typeof(T));
	static T cv<T>(string s) =>
		eq<T,int>()    ? ct<T,int>(int.Parse(s))
	  : eq<T,long>()   ? ct<T,long>(long.Parse(s))
	  : eq<T,double>() ? ct<T,double>(double.Parse(s,System.Globalization.CultureInfo.InvariantCulture))
	  : eq<T,char>()   ? ct<T,char>(s[0])
					   : ct<T,string>(s);
	public static string[] RM<T>(out T a) {
		var z = Console.ReadLine().Split(sp,StringSplitOptions.RemoveEmptyEntries); 
		a = cv<T>(z[0]);
		return z;
	}
	public static string[] RM<T,U>(out T a,out U b) {
		var z = RM<T>(out a); 
        b = cv<U>(z[1]);
		return z;
	}
	public static string[] RM<T,U,V>(out T a,out U b,out V c) {
		var z = RM<T,U>(out a,out b); 
        c = cv<V>(z[2]);
		return z;
	}
	public static string[] RM<T,U,V,W>(out T a,out U b,out V c,out W d) {
		var z = RM<T,U,V>(out a,out b,out c); 
        d = cv<W>(z[3]);
		return z;
	}
	public static string[] RM<T,U,V,W,X>(out T a,out U b,out V c,out W d,out X e) {
		var z = RM<T,U,V,W>(out a,out b,out c,out d); 
        e = cv<X>(z[4]);
		return z;
	}
	public static string[] RM<T,U,V,W,X,Y>(out T a,out U b,out V c,out W d,out X e,out Y f) {
		var z = RM<T,U,V,W,X>(out a,out b,out c,out d,out e); 
        f = cv<Y>(z[5]);
		return z;
	}
	public static string[] RA<T>(out T[] a) {		
		var z = Console.ReadLine().Split(sp,StringSplitOptions.RemoveEmptyEntries);
		a = z.Select(cv<T>).ToArray();
		return z;
	}
	public static string[][] RL<T>(long n,out T[] a) {
		a = new T[n];
		var y = new string[n][];
		for(int i=0;i<n;i++) y[i] = RM(out a[i]);
		return y;
	}
	public static string[][] RL<T,U>(long n,out VT<T,U>[] a) {
		a = new VT<T,U>[n];
		var y = new string[n][];
		for(int i=0;i<n;i++) {
			T o; U p;
			y[i] = RM(out o,out p);
			a[i] = new VT<T,U>(o,p);
		}
		return y;
	}
	public static string[][] RL<T,U,V>(long n,out VT<T,U,V>[] a) {
		a = new VT<T,U,V>[n];
		var y = new string[n][];
		for(int i=0;i<n;i++) {
			T o; U p; V q;
			y[i] = RM(out o,out p,out q);
			a[i] = new VT<T,U,V>(o,p,q);
		}
		return y;
	}
	public static string[][] RL<T,U,V,W>(long n,out VT<T,U,V,W>[] a) {
		a = new VT<T,U,V,W>[n];
		var y = new string[n][];
		for(int i=0;i<n;i++) {
			T o; U p; V q; W r;
			y[i] = RM(out o,out p,out q,out r);
			a[i] = new VT<T,U,V,W>(o,p,q,r);
		}
		return y;
	}
	public static string[][] RX<T>(long n,out T[][] a) {
		a = new T[n][];
		var y = new string[n][];
		for(int i=0;i<n;i++) y[i] = RA(out a[i]);
		return y;
	}

	static void wwp(Action act){
		var s = new Prt(Console.OpenStandardOutput()){AutoFlush = false};
		Console.SetOut(s);
		act();
		Console.Out.Flush();
		s.AutoFlush = true;
		Console.SetOut(s);
	}
	[MethodImpl(256)]
	static string wfm(Type t) =>t.Equals(typeof(double)) ? "{0:F10}" : "{0}";
	public static void WM(params object[] a) {
		wwp(()=>{
			for(int i=0;i<a.Length;i++) {
				var f = wfm(a[i].GetType()) + ((i<a.Length-1) ? " " : Environment.NewLine);
				Console.Write(f,a[i]);
			}
		});
	}
	public static void WA<T>(IList<T> a) {
		wwp(()=>{
			var f = wfm(typeof(T));
			var g = f + " ";
			var h = f + Environment.NewLine;
			for(int i=0;i<a.Count;i++) Console.Write(((i<a.Count-1) ? g : h),a[i]);
		});
	}
	public static void WL<T>(IList<T> a) {
		wwp(()=>{
			var f = wfm(typeof(T)) + Environment.NewLine;
			foreach(T x in a) Console.Write(f,x);
		});
	}


}

#endregion


}


public struct Point : IComparable {
	public double X; public double Y;
	public Point(double a, double b) { X = a; Y = b; }
	public static Point operator+(Point a, Point b) => new Point(a.X + b.X, a.Y + b.Y);
	public static Point operator-(Point a, Point b) => new Point(a.X - b.X, a.Y - b.Y);
	public static Point operator*(Point a, double b) => new Point(a.X * b, a.Y * b);
	public static Point operator/(Point a, double b) => new Point(a.X / b, a.Y / b);
	public int CompareTo(object obj) { 
        if (!(obj is Point)) throw new ArgumentException("Object is not a Point");
        return CompareTo((Point)obj);   
	}
	public int CompareTo(Point b) => (X != b.X) ? X.CompareTo(b.X) : Y.CompareTo(b.Y);
	public override string ToString() => String.Format("({0:f} {1:f})", X, Y);
	
	// 反時計回りに theta 回転
	public Point Rotate(double theta) => new Point(Math.Cos(theta) * X - Math.Sin(theta) * Y, Math.Sin(theta) * X + Math.Cos(theta) * Y);
	public double Norm() => X*X+Y*Y;
	public double Arg() => Math.Atan2(Y, X);
}
// 直線
public struct Line {
	public Point P1; public Point P2;
	public Line(Point a, Point b) { P1 = a; P2 = b; }
	public Line(double x1, double y1, double x2, double y2) : this(new Point(x1, y1), new Point(x2, y2)) { }
	public override string ToString() => String.Format("({0} {1})", P1, P2);
	public Line(double A, double B, double C) // Ax + By = C
	{
		if(Math.Abs(A)<1e-8) {
			P1 = new Point(0, C / B); P2 = new Point(1, C / B);
		}else {
			if(Math.Abs(B)<1e-8) {
				P1 = new Point(C / A, 0); P2 = new Point(C / A, 1);
			} else {
				P1 = new Point(0, C / B); P2 = new Point(C / A, 0);
			}
		}
	}
}
// 線分 Lineと同じ
public struct Segment {
	public Point P1; public Point P2;
	public Segment(Point a, Point b) { P1 = a; P2 = b; }
	public Segment(double x1, double y1, double x2, double y2) : this(new Point(x1, y1), new Point(x2, y2)) { }
	public override string ToString() => String.Format("[{0} {1}]", P1, P2);
	public void Swap() { Point t = P1; P1 = P2; P2 = t; }
}
public struct Circle {
	public Point C;	public double R;
	public Circle(Point c, double r) { C = c; R = Math.Abs(r); }
	public Circle(double cx, double cy, double r) : this(new Point(cx, cy), r) { }
	public override string ToString() => String.Format("({0} {1})", C, R);
}


public static class MyGeom1 {
	private const double EPS = 1e-8;

	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public static bool eq(double a, double b) => Math.Abs(b - a) < EPS;
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public static bool le(double a, double b) => a < b + EPS;
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public static bool lt(double a, double b) => a + EPS < b;

	public static double Radian2degree(double r) => (r * 180.0 / Math.PI);
	public static double Degree2radian(double d) => (d * Math.PI / 180.0);

	// a-b-c の角度のうち小さい方を返す
	public static double GetAngle(Point a, Point b, Point c) {
		double alpha = Math.Atan2(b.Y-a.Y, b.X-a.X), beta = Math.Atan2(c.Y-b.Y, c.X-b.X);
		if(alpha > beta) { double t = alpha; alpha =  beta; beta = t; }
		double theta = (beta - alpha);
		return Math.Min(theta, 2 * Math.PI - theta);
	}

	//外積
	public static double CrossProd(Point a, Point b) => (a.X * b.Y - a.Y * b.X);
	//内積
	public static double DotProd(Point a, Point b) => (a.X * b.X + a.Y * b.Y);

	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_C
	// 点の回転方向  counter-clockwise
	public static long Ccw(Point origin, Point b, Point c) {
		b = b - origin;	c = c - origin;
		double cp = CrossProd(b, c);
		if(lt(0 , cp))               return +1;	// COUNTER_CLOCKWISE
		if(lt(cp , 0))               return -1;	// CLOCKWISE
		if(lt(DotProd(b, c) , 0))    return +2;	// ONLINE_BACK
		if(lt(b.Norm() , c.Norm()))  return -2;	// ONLINE_FRONT
		return 0;							 	// ON_SEGMENT
	}

	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_A
	// 平行判定
	public static bool Parallel(Line a, Line b) => eq(CrossProd(a.P2 - a.P1, b.P2 - b.P1), 0.0);
	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_A
	// 垂直判定
	public static bool Orthogonal(Line a, Line b) => eq(DotProd(a.P1 - a.P2, b.P1 - b.P2), 0.0);

	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_A
	// 射影  直線 l に p から垂線を引いた交点を求める
	public static Point Projection(Line l, Point p) {
		Point d = l.P1 - l.P2;
		double t = DotProd(p - l.P1, d) / d.Norm();
		return l.P1 + d * t;
	}
	public static Point Projection(Segment l, Point p) {
		Point d = l.P1 - l.P2;
		double t = DotProd(p - l.P1, d) / d.Norm();
		return l.P1 + d * t;
	}

	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_1_B
	// 反射  直線 l を対称軸として点 p と線対称にある点を求める
	public static Point Reflection(Line l, Point p) => p + (Projection(l, p) - p) * 2.0;

	// 交差判定
	public static bool Intersect(Point a, Point b) => eq(0, (a-b).Norm());
	public static bool Intersect(Line l,Point p) => Math.Abs(Ccw(l.P1, l.P2, p)) != 1;
	public static bool Intersect(Line l, Line m) => !eq(0 , CrossProd(l.P2 - l.P1, m.P2 - m.P1)) || eq(0, CrossProd(l.P2 - l.P1, m.P2 - l.P1));
	public static bool Intersect(Segment s, Point p) => Ccw(s.P1, s.P2, p) == 0;
	public static bool Intersect(Line l, Segment s) => le(CrossProd(l.P2 - l.P1, s.P1 - l.P1) * CrossProd(l.P2 - l.P1, s.P2 - l.P1) , 0);
	public static bool Intersect(Circle c, Line l) => le(Distance(l, c.C) , c.R);
	public static bool Intersect(Circle c, Point p) => eq(Distance(p - c.C) , c.R);

	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_B
	public static bool Intersect(Segment s, Segment t) => Ccw(s.P1, s.P2, t.P1) * Ccw(s.P1, s.P2, t.P2) <= 0 && Ccw(t.P1, t.P2, s.P1) * Ccw(t.P1, t.P2, s.P2) <= 0;

	public static long Intersect(Circle c, Segment l) {
		Point h = Projection(l, c.C);
		if(lt(c.R * c.R , (h - c.C).Norm())) return 0;	// 交差しない(直線が外側)
		var d1 = Distance(c.C - l.P1);
		var d2 = Distance(c.C - l.P2);
		if(le(d1, c.R) && le(d2, c.R)) return 0;	// 交差しない(線分が内側)
		if(lt(d1, c.R) && lt(c.R, d2) || lt(c.R, d1) && lt(d2, c.R)) return 1;	// １点交差
		if(DotProd(l.P1 - h, l.P2 - h) < 0) return 2;	// ２点交差
		return 0;	// 交差しない(線分が外側)
	}

	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_7_A&lang=jp
	public static long Intersect(Circle c1, Circle c2) {
		if(c1.R < c2.R) { Circle t = c1; c1 = c2; c2 = t;}
		double d = Distance(c1.C - c2.C);
		if(c1.R + c2.R < d)    return 4;	// 外側かつ交差しない
		if(eq(c1.R + c2.R, d)) return 3;	// 外側かつ接する
		if(c1.R - c2.R < d)    return 2;	// 交差する
		if(eq(c1.R - c2.R, d)) return 1;	// 内側かつ接する
		return 0;							// 内側かつ交差しない
	}

	public static double Distance(Point a) => Math.Sqrt(a.Norm());
	public static double Distance(Point a, Point b) => Distance(a - b);
	public static double Distance(Line l, Point p) => Distance(p - Projection(l, p));
	public static double Distance(Line l, Line m) => Intersect(l, m) ? 0 : Distance(l, m.P1);
	public static double Distance(Segment s, Point p) {
		Point r = Projection(s, p);
		if(Intersect(s, r)) return Distance(r - p);
		return Math.Min(Distance(s.P1 - p), Distance(s.P2 - p));
	}

	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_D
	public static double Distance(Segment a, Segment b) {
		if(Intersect(a, b)) return 0;
		return Math.Min(Math.Min(Distance(a, b.P1), Distance(a, b.P2)), Math.Min(Distance(b, a.P1), Distance(b, a.P2)));
	}

	public static double Distance(Line l, Segment s) {
		if(Intersect(l, s)) return 0;
		return Math.Min(Distance(l, s.P1), Distance(l, s.P2));
	}

	public static Point CrossPoint(Line l, Line m) {
		double A = CrossProd(l.P2 - l.P1, m.P2 - m.P1);
		double B = CrossProd(l.P2 - l.P1, l.P2 - m.P1);
		if(eq(Math.Abs(A), 0.0) && eq(Math.Abs(B), 0.0)) return m.P1;
		return m.P1 + (m.P2 - m.P1) * (B / A);
	}

	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_C
	public static Point CrossPoint(Segment l, Segment m) => CrossPoint(new Line(l.P1,l.P2), new Line(m.P1,m.P2));

	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_7_D
	public static Point[] CrossPoint(Circle c, Line l) {
		Point pr = Projection(l, c.C);
		Point e = (l.P2 - l.P1) / Distance(l.P2 - l.P1);
		if(eq(Distance(l, c.C), c.R)) return new Point[]{pr, pr};
		double bas = Math.Sqrt(c.R * c.R - (pr - c.C).Norm());
		return new Point[]{pr - e * bas, pr + e * bas};
	}

	public static Point[] CrossPoint(Circle c, Segment l) {
		Line aa = new Line(l.P1, l.P2);
		var ret = CrossPoint(c, aa);
		if(Intersect(c, l) == 2) return ret;
		if(DotProd(l.P1 - ret[0], l.P2 - ret[0]) < 0) ret[1] = ret[0];
		else ret[0] = ret[1];
		return ret;
	}

	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_7_E
	public static Point[] CrossPoint(Circle c1, Circle c2) {
		double d = Distance(c1.C - c2.C);
		double a = Math.Acos((c1.R * c1.R + d * d - c2.R * c2.R) / (2 * c1.R * d));
		double t = Math.Atan2(c2.C.Y - c1.C.Y, c2.C.X - c1.C.X);
		Point p1 = c1.C + new Point(Math.Cos(t + a) * c1.R, Math.Sin(t + a) * c1.R);
		Point p2 = c1.C + new Point(Math.Cos(t - a) * c1.R, Math.Sin(t - a) * c1.R);
		return new Point[]{p1, p2};
	}

	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_7_F
	// 点 p を通る円 c の接線
	public static Point[] Tangent(Circle c1, Point p2) => CrossPoint(c1, new Circle(p2, Math.Sqrt((c1.C - p2).Norm() - c1.R * c1.R)));

	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_7_G
	// 円 c1, c2 の共通接線
	public static Line[] Tangent(Circle c1, Circle c2) {
		List<Line> ret = new List<Line>();
		if(c1.R < c2.R) { Circle t = c1; c1 = c2; c2 = t; }
		Point pp = c1.C - c2.C;
		double g = pp.Norm();
		if(eq(g, 0)) return ret.ToArray();
		Point u = (c2.C - c1.C) / Math.Sqrt(g);
		Point v = u.Rotate(Math.PI * 0.5);
		foreach(int s in new int[]{-1, 1}) {
			double h = (c1.R + s * c2.R) / Math.Sqrt(g);
			if(eq(1 - h * h, 0)) {
				ret.Add(new Line(c1.C + u * c1.R, c1.C + (u + v) * c1.R));
			} else if(1 - h * h > 0) {
				Point uu = u * h, vv = v * Math.Sqrt(1 - h * h);
				ret.Add(new Line(c1.C + (uu + vv) * c1.R, c2.C - (uu + vv) * c2.R * s));
				ret.Add(new Line(c1.C + (uu - vv) * c1.R, c2.C - (uu - vv) * c2.R * s));
			}
		}
		return ret.ToArray();
	}

}


public static class MyGeom2 {

	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_3_B
	// 凸性判定
	public static bool IsConvex(Point[] p) {
		int n = p.Length;
		for(int i = 0; i < n; i++) {
			if(MyGeom1.Ccw(p[(i + n - 1) % n], p[i], p[(i + 1) % n]) == -1) return false;
		}
		return true;
	}

	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_A
	// 凸包
	public static Point[] ConvexHull(Point[] p) {
		int n = p.Length, k = 0;
		if(n <= 2) return p;
		Array.Sort(p);
		Point[] ch = new Point[2 * n];
		for(int i = 0; i < n; ch[k++] = p[i++]) {
			while(k >= 2 && MyGeom1.le(MyGeom1.CrossProd(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]), 0)) --k;
		}
		for(int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--]) {
			while(k >= t && MyGeom1.le(MyGeom1.CrossProd(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]), 0)) --k;
		}
		Array.Resize(ref ch, k - 1);
		return ch;
	}

	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_3_C
	// 多角形と点の包含判定
	// ret 0:ON 1:IN 2:OUT
	public static long Contains(Point[] Q, Point p) {
		bool f = false;
		for(int i = 0; i < Q.Length; i++) {
			Point a = Q[i] - p, b = Q[(i + 1) % Q.Length] - p;
			if(a.Y > b.Y) { Point t = a; a = b; b = a; }
			if(a.Y <= 0 && 0 < b.Y && MyGeom1.CrossProd(a, b) < 0) f = !f;
			if(MyGeom1.CrossProd(a, b) == 0 && MyGeom1.DotProd(a, b) <= 0) return 0;
		}
		return f ? 1 : 2;
	}

	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1033
	// 線分の重複除去
	public static Segment[] MergeSegments(Segment[] inSegs) {
		List<Segment> segs = new List<Segment>(inSegs);
		Func<int, int, bool> merge_if_able = (i1, i2) => {
			if(!MyGeom1.eq(0, MyGeom1.CrossProd(segs[i1].P2 - segs[i1].P1, segs[i2].P2 - segs[i2].P1))) return false;
			if(MyGeom1.Ccw(segs[i1].P1, segs[i2].P1, segs[i1].P2) == 1 || MyGeom1.Ccw(segs[i1].P1, segs[i2].P1, segs[i1].P2) == -1) return false;
			if(MyGeom1.Ccw(segs[i1].P1, segs[i1].P2, segs[i2].P1) == -2 || MyGeom1.Ccw(segs[i2].P1, segs[i2].P2, segs[i1].P1) == -2) return false;

			segs[i1] = new Segment((segs[i1].P1.CompareTo(segs[i2].P1)<0) ? segs[i1].P1 : segs[i2].P1, (segs[i1].P2.CompareTo(segs[i2].P2)<0) ? segs[i2].P2 : segs[i1].P2);
			return true;
		};

		for(int i = 0; i < segs.Count; i++) {
			if(segs[i].P2.CompareTo(segs[i].P1)<0) segs[i].Swap();
		}
		for(int i = 0; i < segs.Count-1; i++) {
			for(int j = i + 1; j < segs.Count; j++) {
				if(merge_if_able(i, j)) segs.RemoveAt(j--);
			}
		}
		return segs.ToArray();
	}

	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1033
	// 線分アレンジメント  *チェック済
	// 任意の2線分の交点を頂点としたグラフを構築する
	public static List<long>[] SegmentArrangement(Segment[] segs,out Point[] pos) {
		List<Point> ps = new List<Point>();
		int N = segs.Length;
		Point[] sp = new Point[N];
		for(int i = 0; i < N; i++) {
			ps.Add(segs[i].P1);
			ps.Add(segs[i].P2);
			sp[i] = segs[i].P2 - segs[i].P1;
		}
		for(int i = 0; i < N-1; i++) {
			for(int j = i + 1; j < N; j++) {
				if(!MyGeom1.eq(0, MyGeom1.CrossProd(sp[i], sp[j])) && MyGeom1.Intersect(segs[i], segs[j])) ps.Add(MyGeom1.CrossPoint(segs[i], segs[j]));
			}
		}
		ps.Sort();
		int k=1;
		Point bp = ps[0];
		while(k<ps.Count){
			if(MyGeom1.Intersect(bp, ps[k])){ ps.RemoveAt(k); }else{ bp = ps[k++]; }
		}

		int M = ps.Count;
		List<long>[] G = new List<long>[M];
		for(int j = 0; j < M; j++) G[j]= new List<long>();
		for(int i = 0; i < N; i++) {
			List<int> vec = new List<int>();
			for(int j = 0; j < M; j++) {
				if(MyGeom1.Intersect(segs[i], ps[j])) vec.Add(j);
			}
			for(int j = 1; j < vec.Count; j++) {
				G[vec[j - 1]].Add(vec[j]);
				G[vec[j]].Add(vec[j - 1]);
			}
		}
		pos = ps.ToArray();
		return G;
	}

	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_C
	// 凸多角形の切断
	// 直線 l.P1-l.P2 で切断しその左側にできる凸多角形を返す
	public static Point[] ConvexCut(Point[] U, Line l) {
		List<Point> ret = new List<Point>();
		for(int i = 0; i < U.Length; i++) {
			Point now = U[i], nxt = U[(i + 1) % U.Length];
			if(MyGeom1.Ccw(l.P1, l.P2, now) != -1) ret.Add(now);
			if(MyGeom1.Ccw(l.P1, l.P2, now) * MyGeom1.Ccw(l.P1, l.P2, nxt) < 0) ret.Add(MyGeom1.CrossPoint(new Line(now, nxt), l));
		}
		return ret.ToArray();
	}

	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_3_A
	// 多角形の面積
	public static double Area(Point[] p) {
		double A = 0;
		for(int i = 0; i < p.Length; ++i)  A += MyGeom1.CrossProd(p[i], p[(i + 1) % p.Length]);
		return A * 0.5;
	}

	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_7_H
	// 円と多角形の共通部分の面積
	public static double Area(Point[] p, Circle cc) {
		if(p.Length < 3) return 0.0;
		Func<Circle, Point, Point, double> cross_area = null;
		cross_area = (c, a, b) => {
			Point va = c.C - a, vb = c.C - b;
			double f = MyGeom1.CrossProd(va, vb), ret = 0.0;
			if(MyGeom1.eq(f, 0.0)) return ret;
			if(MyGeom1.le(Math.Max(MyGeom1.Distance(va), MyGeom1.Distance(vb)), c.R)) return f;
			if(MyGeom1.le(c.R, MyGeom1.Distance(new Segment(a, b), c.C))) return c.R * c.R * Math.Atan2( -vb.X*va.Y+vb.Y*va.X , vb.X*va.X+vb.Y*va.Y );
			var u = MyGeom1.CrossPoint(c, new Segment(a, b));
			Point[] tot = new Point[]{a, u[0], u[1], b};
			for(int i = 0; i + 1 < tot.Length; i++) ret += cross_area(c, tot[i], tot[i + 1]);
			return ret;
		};
		double A = 0;
		for(int i = 0; i < p.Length; i++) A += cross_area(cc, p[i], p[(i + 1) % p.Length]);

		return A;
	}

	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_B
	// 凸多角形の直径(最遠頂点対間距離)
	public static double ConvexDiameter(Point[] p) {
		int N = p.Length;
		int si = 0, sj = 0;
		for(int k = 1; k < N; k++) {
			if(p[k].Y > p[si].Y) si = k;
			if(p[k].Y < p[sj].Y) sj = k;
		}
		double maxdis = (p[si] - p[sj]).Norm();

		int maxi, maxj, i, j;
		i = maxi = si;
		j = maxj = sj;
		do {
			if(MyGeom1.CrossProd(p[(i + 1) % N] - p[i], p[(j + 1) % N] - p[j]) >= 0) { j = (j + 1) % N; } else { i = (i + 1) % N; }
			double nm = (p[i] - p[j]).Norm();
			if(nm > maxdis) { maxdis = nm; maxi = i; maxj = j; }
		} while(i != si || j != sj);
		return Math.Sqrt(maxdis);
	}

	// https://tubo28.me/compprog/algorithm/minball/
	// 概要 2 次元の点集合を入力とし，それらを内包するような半径最小の円を出力する． 点をランダムにシャッフルして前から順に最小包含円を大きくしていく． 
	// k番目の点を見たときに，更新する必要がある確率は O(1/k) となり，そのとき更新に O(k) かかる． 期待値を取ると ∑nk=1O(1/k)O(k)=O(n)が得られる．計算量期待値 O(n)
	public static Circle Minball(Point[] p) {
		int n = p.Length;

		if (n == 1) return new Circle(p[0],0);

		Func<Point,Point,Point,Circle> make_circle_3 = (a,b,c) =>{
			double A = (b - c).Norm(), B = (c - a).Norm(), C = (a - b).Norm(), S = MyGeom1.CrossProd(b - a, c - a);
			Point pp = (a * A * (B + C - A) + b * B * (C + A - B) + c * C * (A + B - C)) / (4 * S * S);
			double r2 = (pp - a).Norm();
			return new Circle(pp, r2);
		};

		Func<Point,Point,Circle> make_circle_2 = (a,b) =>{
			Point c = (a + b) * 0.5;
			double r2 = (a - c).Norm();
			return new Circle(c, r2);
		};

		Func<Point,Circle,bool> in_circle = (a,c) =>{
			return MyGeom1.le((a - c.C).Norm() , c.R);
		};

		Circle cc = make_circle_2(p[0], p[1]);

		// MiniDisc
		for (int i = 2; i < n; ++i) {
			if (!in_circle(p[i], cc)) {
				// MiniDiscWithPoint
				cc = make_circle_2(p[0], p[i]);
				for (int j = 1; j < i; ++j) {
					if (!in_circle(p[j], cc)) {
						// MiniDiscWith2Points
						cc = make_circle_2(p[i], p[j]);
						for (int k = 0; k < j; ++k) {
							if (!in_circle(p[k], cc)) {
								cc = make_circle_3(p[i], p[j], p[k]);
							}
						}
					}
				}
			}
		}
		return new Circle(cc.C, Math.Sqrt(cc.R));
	}

	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_5_A
	// 最近点対  *チェック済
	public static double ClosestPair(Point[] ps) {
		if(ps.Length <= 1)  throw new ArgumentException("Invalid length", "ps.Length");
		Array.Sort(ps);

		Comparison<Point> compare_y = (a, b) => (a.Y.CompareTo(b.Y));
		Point[] beet = new Point[ps.Length];
		Point[] work = new Point[ps.Length/2+1];

		Func<int,int,double> rec = null;
		rec = (left, right) => {
			if(right - left <= 1) return long.MaxValue;
			int mid = (left + right) >> 1;
			var x = ps[mid].X;
			var ret = Math.Min(rec(left, mid), rec(mid, right));
			merge(ps, left, mid, right, work, compare_y);
			int ptr = 0;
			for(int i = left; i < right; i++) {
				if(Math.Abs(ps[i].X - x) >= ret) continue;
				for(int j = 0; j < ptr; j++) {
					var luz = ps[i] - beet[ptr - j - 1];
					if(luz.Y >= ret) break;
					ret = Math.Min(ret, MyGeom1.Distance(luz));
				}
				beet[ptr++] = ps[i];
			}
			return ret;
		};
		return rec(0, ps.Length);
	}
	private static void merge<T>(T[] a, int begin, int mid, int end, T[] work, Comparison<T> comp) {
		if((end - begin) < 5) {
			// 挿入ソートは利用しなくてもよい
			for (int i = begin + 1; i < end; i++)
				for (int j = i; j > begin && comp(a[j-1], a[j]) > 0; --j) {
					T t = a[j]; a[j] = a[j-1]; a[j-1] = t;
				}
		} else {
			int i, j, k;
			for (i = begin, j = 0; i != mid; ++i, ++j) work[j] = a[i];
			mid -= begin;
			for (j = 0, k = begin; i != end && j != mid; ++k) {
				if (comp(a[i], work[j]) < 0) { a[k] = a[i++]; } else { a[k] = work[j++]; }
			}
			for (; i < end; ++i, ++k) a[k] = a[i];
			for (; j < mid; ++j, ++k) a[k] = work[j];
		}
	}


}




Measured memory_bytes: 13908