Problem: You are given a convex polygon P with n distinct vertices p1, p2, ..., pn. Vertex pi has coordinates (xi, yi) in the 2D plane. These vertices are listed in clockwise order.

You can choose a real number D and move each vertex of the polygon a distance of at most D from their original positions.

Find the maximum value of D such that no matter how you move the vertices, the polygon does not intersect itself and stays convex.

Input

The first line has one integer n (4 ≤ n ≤ 1 000) — the number of vertices.

The next n lines contain the coordinates of the vertices. Line i contains two integers xi and yi ( - 109 ≤ xi, yi ≤ 109) — the coordinates of the i-th vertex. These points are guaranteed to be given in clockwise order, and will form a strictly convex polygon (in particular, no three consecutive points lie on the same straight line).

Output

Print one real number D, which is the maximum real number such that no matter how you move the vertices, the polygon stays convex.

Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely, let's assume that your answer is a and the answer of the jury is b. The checker program will consider your answer correct if <image>.

Examples

Input

4
0 0
0 1
1 1
1 0


Output

0.3535533906


Input

6
5 0
10 0
12 -4
10 -8
5 -8
3 -4


Output

1.0000000000

Note

Here is a picture of the first sample

<image>

Here is an example of making the polygon non-convex.

<image>

This is not an optimal solution, since the maximum distance we moved one point is  ≈ 0.4242640687, whereas we can make it non-convex by only moving each point a distance of at most  ≈ 0.3535533906.

Solution (in JAVA):

Solution:
import java.awt.Point;
import java.awt.geom.Line2D;
import java.util.Scanner;

public class d {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		Vector[] ps = new Vector[n];
		for(int i=0;i<n;i++)
			ps[i] = new Vector(in.nextInt(), in.nextInt());
		double ans = ps[0].sub(ps[1]).mag();
		for(int i=0;i<n;i++) {
			Vector a = ps[i], b = ps[(i+1)%n], c = ps[(i+2)%n];
			double dist = Vector.pointLineSegDist(a, c, b);
			ans = Math.min(ans, dist/2);
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(i == j) continue;
				ans = Math.min(ans, ps[i].sub(ps[j]).mag());
			}
		}
		System.out.printf("%.9f\n", ans);
	}
	static class Vector implements Comparable<Vector> {
	    public double x, y, z; //%
	    public double x0 = 0, y0 = 0, z0 = 0; //%
	    public static double epsilon = 1e-6; //%
	    public static Vector ORIGIN = new Vector(0, 0, 0); //%
	    public static int curId = 0; //%
	    public int id = Vector.curId++; //%

	    //#
	    //Constructor for normal vector
	    public Vector(double xx, double yy, double zz) {
	        x = xx;
	        y = yy;
	        z = zz;
	    }

	    // Constructor for 2d normal vector
	    public Vector(double xx, double yy) {
	        x = xx;
	        y = yy;
	        z = 0.0;
	    }

	    //Constructor for ray/line vector
	    public Vector(Vector a, Vector b) {
	        x = b.x - (x0 = a.x);
	        y = b.y - (y0 = a.y);
	        z = b.z - (z0 = a.z);
	    }

	    //$
	    
	    //#
	    public static boolean equals(double a, double b) {
	        return Math.abs(a - b) < epsilon;
	    }

	    public Vector add(Vector v) {
	        return new Vector(x + v.x, y + v.y, z + v.z);
	    }

	    public Vector sub(Vector v) {
	        return new Vector(x - v.x, y - v.y, z - v.z);
	    }
	    
	    public Vector scale(double s) {
	        return new Vector(new Vector(x0, y0, z0), new Vector((x * s) + x0, (y * s) + y0, (z * s) + z0));
	    }

	    public double mag() {
	        return Math.sqrt((x*x) + (y*y) + (z*z));
	    }
	    
	    public double mag2() {
	        return dot(this);
	    }

	    public double dot(Vector v) {
	        return (x * v.x) + (y * v.y) + (z * v.z);
	    }

	    //$
	    
	    public Vector cross(Vector v) { return new Vector(y*v.z - z*v.y, z*v.x - x*v.z, x*v.y - y*v.x); }

	    //#
	    public Vector normalize() {
	        double mag = mag();
	        return new Vector(new Vector(x0, y0, z0), new Vector((x / mag) + x0, (y / mag) + y0, (z / mag) + z0));
	    }
	    //$
	    
	    // return this vector rotated 90 degrees clockwise //%
	    public Vector orthoCW() { return new Vector(y, -x, z); }

	    // return this vector rotated 90 degrees counter-clockwise //%
	    public Vector orthoCCW() { return new Vector(-y, x, z); }

	    //Returns a rotated vector rotated on the XY plane around (c.x, c.y) (***Z value will NOT change***)
	    public Vector rotate(Vector c, double a) { return new Vector(new Vector(c.x, c.y, z0), this).rotate(a); }

	    //Returns a rotated vector rotated on the XY plane around (x0, y0, z0) (***Z value will NOT change***)
	    public Vector rotate(double a) {
	        return new Vector(new Vector(x0, y0, z0), new Vector((x*Math.cos(a)) - (y*Math.sin(a)) + x0, (x*Math.sin(a)) + (y*Math.cos(a)) + y0, z + z0));
	    }

	    public boolean pointOnLine(Vector p) {
	        if(equals(x, 0.0)) return equals(p.x, x0);
	        return equals(p.y - y0, (y/x) * (p.x - x0));
	    }

	    //#
	    public boolean intersects(Vector v) {
	        return intersect(v) != null;
	    }
	    //$
	    
	    //Returns a 2d vector of the intersection //%
	    //returns null if the lines don't intersect or are on top of each other //%
	    public Vector intersect(Vector v) {
	        double x1 = x0, x2 = x + x0, y1 = y0, y2 = y + y0;
	        double x3 = v.x0, x4 = v.x0 + v.x, y3 = v.y0, y4 = v.y + v.y0;

	        if(equals((x1 - x2) * (y3 - y4), (y1 - y2) * (x3 - x4))) return null;

	        double newX = ((x1 * y2) - (y1 * x2)) * (x3 - x4);
	        newX -= (x1 - x2) * ((x3 * y4) - (y3 * x4));
	        newX /= (x1 - x2) * (y3 - y4) - ((y1 - y2) * (x3 - x4));

	        double newY = ((x1 * y2) - (y1 * x2)) * (y3 - y4);
	        newY -= (y1 - y2) * ((x3 * y4) - (y3 * x4));
	        newY /= (x1 - x2) * (y3 - y4) - ((y1 - y2) * (x3 - x4));

	        return new Vector(newX, newY, 0.0);
	    }
	    
	    //Returns the point of intersection between this line and the line/vector v. //%
	    //Returns null if the lines are parallel or skew //%
	    public Vector intersect3D(Vector v) {
	        if(equals(cross(v).mag(), 0.0)) return null; //The lines are parallel
	        double s, t;
	        if(!equals(x, 0.0)) {
	            if(!equals(v.y, v.x * y / x)) {
	                s = y0 - v.y0 + (y * (v.x0 - x0) / x);
	                s /= v.y - (v.x * y / x);
	            } else if(!equals(v.z, v.x * z / x)) {
	                s = z0 - v.z0 + (z * (v.x0 - x0) / x);
	                s /= v.z - (v.x * z / x);
	            } else return null;
	            t = (v.x0 + (s * v.x) - x0) / x;
	        } else if(!equals(y, 0.0)) {
	            if(!equals(v.x, v.y * x / y)) {
	                s = x0 - v.x0 + (x * (v.y0 - y0) / y);
	                s /= v.x - (v.y * x / y);
	            } else if(!equals(v.z, v.y * z / y)) {
	                s = z0 - v.z0 + (z * (v.y0 - y0) / y);
	                s /= v.z - (v.y * z / y);
	            } else return null;
	            t = (v.y0 + (s * v.y) - y0) / y;
	        } else if(!equals(z, 0.0)) {
	            if(!equals(v.y, v.z * y / z)) {
	                s = y0 - v.y0 + (y * (v.z0 - z0) / z);
	                s /= v.y - (v.z * y / z);
	            } else if(!equals(v.x, v.z * x / z)) {
	                s = x0 - v.x0 + (x * (v.z0 - z0) / z);
	                s /= v.x - (v.z * x / z);
	            } else return null;
	            t = (v.z0 + (s * v.z) - z0) / z;
	        } else return null;
	        double newX = x0 + (t * x);
	        double newX2 = v.x0 + (s * v.x);

	        double newY = y0 + (t * y);
	        double newY2 = v.y0 + (s * v.y);

	        double newZ = z0 + (t * z);
	        double newZ2 = v.z0 + (s * v.z);

	        if(!equals(newX, newX2) || !equals(newY, newY2) || !equals(newZ, newZ2)) return null; //The lines are skew
	        return new Vector(newX, newY, newZ);
	    }

	    //Gets angle between this vector and vector v (range: [0, pi] )
	    public double angleBetween(Vector v) {
	        return Math.acos( Math.max(-1, Math.min(1, dot(v) / (mag() * v.mag()))) );
	    }

	    //Gets angle between this vector and vector v (range (-pi, pi] )
	    public double angleTo(Vector v) {
	        //Can be changed to " > 0.0" to return -1 if the vectors are parallel //%
	        //(useful for checking if a point is to left/right OR on the line //%
	        if(this.cross(v).z >= 0.0)
	            return Math.acos( Math.max(-1.0, Math.min(1.0, this.dot(v) / (this.mag() * v.mag()))) );
	        return - Math.acos( Math.max(-1.0, Math.min(1.0, this.dot(v) / (this.mag() * v.mag()))) );
	    }
	    
	    //#
	    //Returns only the sign of the angle between this vector and the vector v on the XY plane.
	    //+1 for to the left, -1 otherwise(to the right or straight)
	    public int angleToSign(Vector v) {
	        return this.cross(v).z > 0.0 ? 1 : -1;
	    }
	    //$
	    
	    //Gets the value of sin(theta) and cos(theta) needed to rotate this vector to the vector v
	    //Only works on the XY plane currently
	    public double[] getSinCosTo(Vector v) {
	        double mags = mag() * v.mag();
	        return new double[]{cross(v).z / mags, dot(v) / mags};
	    }
	    
	    //#
	    //Returns [0.0, 4.0] which allows these vectors to be sorted by angle
	    //0.0 is a vector that is directly to the right
	    public double getSortableAngleTo(Vector v) {
	        Vector r = v.sub(this);
	        double dot = r.dot(new Vector(1.0, 0.0)) / r.mag();
	        dot = 1.0 - dot;
	        if(r.y < 0.0)
	            dot = 4.0 - dot;
	        return dot;
	    }
	    //$

	    //#
	    //Checks if two vectors are orthogonal to each other
	    public boolean isOrthogonal(Vector v) {
	        return equals(this.dot(v), 0.0);
	    }
	    //$

	    //#
	    //Checks if two vectors are in parallel
	    public boolean isParallel(Vector v) {
	        return equals(this.cross(v).mag(), 0.0);
	    }
	    //$

	    /* Static functions using vectors */ //%
	    
	    //#
	    //Returns the area of a triangle defined by three vertices
	    public static double triangleArea(Vector p1, Vector p2, Vector p3) {
	        return p2.sub(p1).cross(p3.sub(p1)).mag() / 2.0;
	    }
	    //$
	    
	    //#
	    //Returns only the sign of the angle between (p0, p1) and (p0, p2)
	    //+1 for to the left, -1 otherwise(to the right or straight)
	    public static int angleToSign(Vector p0, Vector p1, Vector p2) {
	        return new Vector(p0, p1).angleToSign(new Vector(p0, p2));
	    }
	    //$
	    
	    //#
	    //Check if a point is INSIDE a triangle defined by three points
	    public static boolean pointInTriangle(Vector a, Vector b, Vector c, Vector p) {
	        double angle = 0.0;
	        angle += a.sub(p).angleBetween(b.sub(p));
	        angle += b.sub(p).angleBetween(c.sub(p));
	        angle += a.sub(p).angleBetween(c.sub(p));
	        return Vector.equals(angle, Math.PI * 2.0);
	    }
	    //$

	    //#
	    //Returns the distance from a point to a line segment defined by two points //%
	    public static double pointLineDist(Vector l1, Vector l2, Vector p) {
	        Vector line = l2.sub(l1);  double l = line.dot(line);
	        double t = p.sub(l1).dot(line) / l;  return line.scale(t).add(l1).sub(p).mag();
	    }
	    //$
	    
	    //Returns the distance from a point to a line segment defined by two points //%
	    public static double pointLineSegDist(Vector l1, Vector l2, Vector p) {
	        Vector line = l2.sub(l1); double l = line.dot(line);
	        double t = p.sub(l1).dot(line) / l;
	        if (t < 0)  return l1.sub(p).mag(); //Remove this line
	        else if(t > 1)  return l2.sub(p).mag(); // and this line to make pointLineDist
	        return line.scale(t).add(l1).sub(p).mag();
	    }

	    //Returns a vector where p is reflected past the line formed by l1 and l2
	    public static Vector reflect(Vector l1, Vector l2, Vector p) {
	        Vector line = l2.sub(l1);  double l = line.dot(line);
	        double t = p.sub(l1).dot(line) / l;  Vector q = line.scale(t).add(l1);
	        return q.add(q.sub(p));
	    }
	    
	    //Refelcts this vector across the vector n
	    public Vector reflect(Vector n) { n = n.normalize();  return sub(n.scale(2.0*dot(n))); }

	    //#
	    public int compareTo(Vector p) {
	        if (y == p.y) return Double.compare(x, p.x);
	        return Double.compare(y, p.y);
	    }
	    //$
	    
	    // Compares a and b with whichever comes first in a positive circular sweep
	    // Works best for longs
	    public static int compare(Vector a, Vector b) {
	        int qA = 0, qB = 0;

	        if(a.x < 0 && a.y >= 0) qA = 1;
	        if(a.x < 0 && a.y < 0) qA = 2;
	        if(a.x >= 0 && a.y < 0) qA = 3;

	        if(b.x < 0 && b.y >= 0) qB = 1;
	        if(b.x < 0 && b.y < 0) qB = 2;
	        if(b.x >= 0 && b.y < 0) qB = 3;

	        if(qA == qB) {
	            Vector cross = a.cross(b);  if(cross.z == 0) return 0;
	            if(cross.z > 0) return -1;  else  return 1;
	        }

	        return Integer.compare(qA, qB);
	    }
	    
	    //#
	    public String toString() {
	        if(equals(x0, 0.0) && equals(y0, 0.0) && equals(z0, 0.0))
	            return String.format("<%.2f, %.2f, %.2f>", x, y, z);
	        return String.format("<%.2f + %.2ft, %.2f + %.2ft, %.2f + %.2ft>", x0, x, y0, y, z0, z);
	    } //$
	}
}