#include <bits/stdc++.h>
using namespace std;
//基本セット
const double EPS=1e-10;
const double pi=3.141592653589793238;
bool equal(double a,double b){return fabs(a-b)<EPS;}
//3点の状態を表現
static const int CCW_COUNTER_CLOCKWISE=1;//p0,p1,p2が反時計回り
static const int CCW_CLOCKWISE=-1;//p0,p1,p2が時計回り
static const int CCW_ONLINE_BACK=2;//p2,p0,p1がこの順で同一直線上
static const int CCW_ONLINE_FRONT=-2;//p0,p1,p2がこの順で同一直線上
static const int CCW_ON_SEGMENT=0;//線分p0-p1上にp2
//2円の状態を表現
static const int ICC_SEPARATE=4;//離れている
static const int ICC_CIRCUMSCRIBE=3;//外接している
static const int ICC_INTERSECT=2;//交わる
static const int ICC_INSCRIBE=1;//内接している
static const int ICC_CONTAIN=0;//内包する
//点
struct point{
	double x,y;
	point(){}
	point(double x,double y):x(x),y(y){}
	point operator+(point p){return point(x+p.x,y+p.y);}
	point operator-(point p){return point(x-p.x,y-p.y);}
	point operator*(double k){return point(x*k,y*k);}
	point operator/(double k){return point(x/k,y/k);}
	double norm(){return x*x+y*y;}
	double abs(){return sqrt(norm());}
	bool operator<(const point &p)const{
		return !equal(x,p.x)?x<p.x:!equal(y,p.y)?y<p.y:0;
	}
	bool operator==(const point &p)const{
		return fabs(x-p.x)<EPS&&fabs(y-p.y)<EPS;
	}
};
//点基本セット
double norm(point a){
	return a.x*a.x+a.y*a.y;
}
double abs(point a){
	return sqrt(norm(a));
}
double dot(point a,point b){
	return a.x*b.x+a.y*b.y;
}
double det(point a,point b){
	return a.x*b.y-a.y*b.x;
}
bool sort_x(point a,point b){
	return a.x!=b.x?a.x<b.x:a.y<b.y;
}
bool sort_y(point a,point b){
	return a.y!=b.y?a.y<b.y:a.x<b.x;
}
//ベクトル、多角形
typedef point Vector;
typedef vector<point> polygon;
//線分
struct segment{
	point p1,p2;
	segment(){}
	segment(point p1,point p2):p1(p1),p2(p2){}
};
//直線
typedef segment line;
//円
struct circle{
	point c;
	double r;
	circle(){}
	circle(point c,double r):c(c),r(r){}
};
//わからん
struct EndPoint{
	point p;
	int seg,st;
	EndPoint(){}
	EndPoint(point p,int seg,int st):p(p),seg(seg),st(st){}
	bool operator<(const EndPoint &ep)const{
		return p.y!=ep.p.y?p.y<ep.p.y:st<ep.st;
	}
};
//点多角形線分直線円入出力楽ちんセット
istream &operator>>(istream &is,point &p){
	is>>p.x>>p.y;
	return is;
}
ostream &operator<<(ostream &os,point p){
	os<<fixed<<setprecision(12)<<p.x<<" "<<p.y;
	return os;
}
istream &operator>>(istream &is,polygon &p){
	for(int i=0;i<p.size();i++){
		is>>p[i];
	}
	return is;
}
istream &operator>>(istream &is,segment &s){
	is>>s.p1>>s.p2;
	return is;
}
istream &operator>>(istream &is,circle &c){
	is>>c.c>>c.r;
	return is;
}
//直線の直行平行判定
point orth(point p){
	return point(-p.y,p.x);
}
bool isOrthogonal(Vector a,Vector b){
	return equal(dot(a,b),0.0);
}
bool isOrthogonal(point a1,point a2,point b1,point b2){
	return isOrthogonal(a1-a2,b1-b2);
}
bool isOrthogonal(line l1,line l2){
	return equal(dot(l1.p2-l1.p1,l2.p2-l2.p1),0.0);
}
bool isParallel(Vector a,Vector b){
	return equal(det(a,b),0.0);
}
bool isParallel(point a1,point a2,point b1,point b2){
	return isParallel(a1-a2,b1-b2);
}
bool isParallel(line l1,line l2){
	return equal(det(l1.p2-l1.p1,l2.p2-l2.p1),0.0);
}
//同一直線判定
bool isSame(line l1,line l2){
	return equal(det(l1.p2-l1.p1,l2.p2-l1.p1),0.0);
}
bool isSame(point a1,point a2,point b1,point b2){
	return isSame(line(a1,a2),line(b1,b2));
}
//射影対照わからんわからん
point project(line l,point p){
	Vector base=l.p2-l.p1;
	double r=dot(p-l.p1,base)/norm(base);
	return l.p1+base*r;
}
point reflect(line l,point p){
	return p+(project(l,p)-p)*2.0;
}
double arg(Vector p){
	return atan2(p.y,p.x);
}
Vector polar(double a,double r){
	return point(cos(r)*a,sin(r)*a);
}
//諸事情により
int ccw(point p0,point p1,point p2);
bool intersectSS(point p1,point p2,point p3,point p4);
bool intersectSS(segment s1,segment s2);
bool intersectPS(polygon p,segment s);
int intersectCC(circle c1,circle c2);
bool intersectSC(segment s,circle c);
int intersectCS(circle c,segment s);
double getDistanceLP(line l,point p);
double getDistanceSP(segment s,point p);
double getDistanceSS(segment s1,segment s2);
point getCrossPointSS(segment s1,segment s2);
point getCrossPointLL(line l1,line l2);
polygon getCrossPointCL(circle c,line l);
polygon getCrossPointCS(circle c,segment s);
polygon getCrossPointCC(circle c1,circle c2);
int isContain(polygon g,point p);
polygon andrewScan(polygon s);
polygon convex_hull(polygon ps);
double diameter(polygon p);
bool isConvex(polygon p);
double area(polygon p);
double area(circle c1,circle c2);
double area(polygon ps,circle c);
polygon convexCut(polygon p,line l);
line bisector(point p1,point p2);
Vector translate(Vector v,double theta);
vector<line> corner(line l1,line l2);
double closest_pair(polygon &a,int l,int r);
int manhattanIntersection(vector<line> ss,const int inf);
//３点の状態判定
int ccw(point p0,point p1,point p2){
	Vector a=p1-p0;
	Vector b=p2-p0;
	if(det(a,b)>EPS){
		return CCW_COUNTER_CLOCKWISE;
	}else if(det(a,b)<-EPS){
		return CCW_CLOCKWISE;
	}else if(dot(a,b)<-EPS){
		return CCW_ONLINE_BACK;
	}else if(norm(a)<norm(b)){
		return CCW_ONLINE_FRONT;
	}else{
		return CCW_ON_SEGMENT;
	}
}
//2線分、多角形と線分、2円、線分と円、円と線分の交差判定
bool intersectSS(point p1,point p2,point p3,point p4){
	return (ccw(p1,p2,p3)*ccw(p1,p2,p4)<=0&&ccw(p3,p4,p1)*ccw(p3,p4,p2)<=0);
}
bool intersectSS(segment s1,segment s2){
	return intersectSS(s1.p1,s1.p2,s2.p1,s2.p2);
}
bool intersectPS(polygon p,segment s){
	int n=p.size();
	for(int i=0;i<n;i++){
		if(intersectSS(segment(p[i],p[(i+1)%n]),s)){
			return 1;
		}
	}
	return 0;
}
int intersectCC(circle c1,circle c2){
	if(c1.r<c2.r){
		swap(c1,c2);
	}
	double d=abs(c1.c-c2.c);
	double r=c1.r+c2.r;
	if(equal(d,r)){
		return ICC_CIRCUMSCRIBE;
	}else if(d>r){
		return ICC_SEPARATE;
	}else if(equal(d+c2.r,c1.r)){
		return ICC_INSCRIBE;
	}else if(d+c2.r<c1.r){
		return ICC_CONTAIN;
	}else{
		return ICC_INTERSECT;
	}
}
bool intersectSC(segment s,circle c){
	return getDistanceSP(s,c.c)<=c.r;
}
int intersectCS(circle c,segment s){
	if(norm(project(s,c.c)-c.c)-c.r*c.r>EPS){
		return 0;
	}
	double d1=abs(c.c-s.p1),d2=abs(c.c-s.p2);
	if(d1<c.r+EPS&&d2<c.r+EPS){
		return 0;
	} if((d1<c.r-EPS&&d2>c.r+EPS)||(d1>c.r+EPS&&d2<c.r-EPS)){
		return 1;
	}
	point h=project(s,c.c);
	if(dot(s.p1-h,s.p2-h)<0){
		return 2;
	}else{
		return 0;
	}
}
//直線と点、線分と点、線分と線分の距離
double getDistanceLP(line l,point p){
	return abs(det(l.p2-l.p1,p-l.p1)/abs(l.p2-l.p1));
}
double getDistanceSP(segment s,point p){
	if(dot(s.p2-s.p1,p-s.p1)<0.0){
		return abs(p-s.p1);
	}else if(dot(s.p1-s.p2,p-s.p2)<0.0){
		return abs(p-s.p2);
	}else{
		return getDistanceLP(s,p);
	}
}
double getDistanceSS(segment s1,segment s2){
	if(intersectSS(s1,s2)){
		return 0.0;
	}else{
		return min(min(getDistanceSP(s1,s2.p1),getDistanceSP(s1,s2.p2)),min(getDistanceSP(s2,s1.p1),getDistanceSP(s2,s1.p2)));
	}
}
//2線分、2直線、円と直線、円と線分、2円の交点
point getCrossPointSS(segment s1,segment s2){
	for(int i=0;i<2;i++){
		if(getDistanceSP(s1,s2.p1)<EPS){
			return s2.p1;
		}else if(getDistanceSP(s1,s2.p2)<EPS){
			return s2.p2;
		}else{
			swap(s1,s2);
		}
	}
	Vector base=s2.p2-s2.p1;
	double d1=abs(det(base,s1.p1-s2.p1));
	double d2=abs(det(base,s1.p2-s2.p1));
	double t=d1/(d1+d2);
	return s1.p1+(s1.p2-s1.p1)*t;
}
point getCrossPointLL(line l1,line l2){
	double a=det(l1.p2-l1.p1,l2.p2-l2.p1);
	double b=det(l1.p2-l1.p1,l1.p2-l2.p1);
	if(abs(a)<EPS&&abs(b)<EPS){
		return l2.p1;
	}else{
		return l2.p1+(l2.p2-l2.p1)*(b/a);
	}
}
polygon getCrossPointCL(circle c,line l){
	polygon ps;
	point pr=project(l,c.c);
	Vector e=(l.p2-l.p1)/abs(l.p2-l.p1);
	if(equal(getDistanceLP(l,c.c),c.r)){
		ps.emplace_back(pr);
		return ps;
	}
	double base=sqrt(c.r*c.r-norm(pr-c.c));
	ps.emplace_back(pr+e*base);
	ps.emplace_back(pr-e*base);
	return ps;
}
polygon getCrossPointCS(circle c,segment s){
	line l(s);
	polygon res=getCrossPointCL(c,l);
	if(intersectCS(c,s)==2){
		return res;
	}else if(res.size()>1u){
		if(dot(l.p1-res[0],l.p2-res[0])>0){
			swap(res[0],res[1]);
		}else{
			res.pop_back();
		}
	}
	return res;
}
polygon getCrossPointCC(circle c1,circle c2){
	polygon p(2);
	double d=abs(c1.c-c2.c);
	double a=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));
	double t=arg(c2.c-c1.c);
	p[0]=c1.c+polar(c1.r,t+a);
	p[1]=c1.c+polar(c1.r,t-a);
	return p;
}
//多角形に点が含まれるか
//in:2 on:1 out:0
int isContain(polygon g,point p){
	bool x=false;
	for(int i=0;i<g.size();i++){
		point a=g[i]-p,b=g[(i+1)%g.size()]-p;
		if(fabs(det(a,b))<EPS&&dot(a,b)<EPS){
			return 1;
		}else if(a.y>b.y){
			swap(a,b);
		}
		if(a.y<EPS&&EPS<b.y&&det(a,b)>EPS){
			x=!x;
		}
	}
	return (x?2:0);
}
//凸性判定
bool isConvex(polygon p){
	int n=p.size();
	for(int i=0;i<n;i++){
		if(ccw(p[(i-1+n)%n],p[i],p[(i+1)%n])==-1){
			return 0;
		}
	}
	return 1;
}
//一番左の点から凸包
polygon andrewScan(polygon s){
	polygon u,l;
	if(s.size()<3){
		return s;
	}
	sort(s.begin(),s.end());
	u.push_back(s[0]);u.push_back(s[1]);
	l.push_back(s[s.size()-1]);l.push_back(s[s.size()-2]);
	for(int i=2;i<s.size();i++){
		for(int j=u.size();j>=2&&ccw(u[j-2],u[j-1],s[i])!=CCW_CLOCKWISE;j--){
			u.pop_back();
		}
		u.push_back(s[i]);
	}
	for(int i=s.size()-3;i>=0;i--){
		for(int j=l.size();j>=2&&ccw(l[j-2],l[j-1],s[i])!=CCW_CLOCKWISE;j--){
			l.pop_back();
		}
		l.push_back(s[i]);
	}
	reverse(l.begin(),l.end());
	for(int i=u.size()-2;i>=1;i--){
		l.push_back(u[i]);
	}
	return l;
}
//一番下の一番左の点から反時計回りに凸包
polygon convex_hull(polygon ps){
	sort(ps.begin(),ps.end(),sort_y);
	int k=0;
	polygon qs(ps.size()*2);
	for(int i=0;i<ps.size();i++){
		while(k>1&&det(qs[k-1]-qs[k-2],ps[i]-qs[k-1])<0){
			k--;
		}
		qs[k++]=ps[i];
	}
	for(int i=ps.size()-2,t=k;i>=0;i--){
		while(k>t&&det(qs[k-1]-qs[k-2],ps[i]-qs[k-1])<0){
			k--;
		}
		qs[k++]=ps[i];
	}
	qs.resize(k-1);
	return qs;
}
//凸多角形を直線で切断し左側の多角形を求める
polygon convexCut(polygon p,line l){
	polygon q;
	for(int i=0;i<p.size();i++){
		point a=p[i],b=p[(i+1)%p.size()];
		if(ccw(l.p1,l.p2,a)!=-1){
			q.push_back(a);
		}
		if(ccw(l.p1,l.p2,a)*ccw(l.p1,l.p2,b)<0){
			q.push_back(getCrossPointLL(line(a,b),l));
		}
	}
	return q;
}
//多角形の最遠頂点対間距離
double diameter(polygon p){
	int n=p.size();
	if(n==2){
		return abs(p[0]-p[1]);
	}
	int i=0,j=0;
	for(int k=0;k<n;k++){
		if(p[i]<p[k]){
			i=k;
		}
		if(!(p[j]<p[k])){
			j=k;
		}
	}
	double res=0;
	int si=i,sj=j;
	while(i!=sj||j!=si){
		res=max(res,abs(p[i]-p[j]));
		if(det(p[(i+1)%n]-p[i],p[(j+1)%n]-p[j])<0.0){
			i=(i+1)%n;
		}else{
			j=(j+1)%n;
		}
	}
	return res;
}
//多角形の最近頂点対間距離
double closest_pair(polygon &a,int l=0,int r=-1){
	if(r<0){
		r=a.size();
		sort(a.begin(),a.end(),sort_x);
	}
	if(r-l<=1){
		return abs(a[0]-a[1]);
	}
	int m=(l+r)>>1;
	double x=a[m].x;
	double d=min(closest_pair(a,l,m),closest_pair(a,m,r));
	inplace_merge(a.begin()+l,a.begin()+m,a.begin()+r,sort_y);
	polygon b;
	for(int i=l;i<r;i++){
		if(fabs(a[i].x-x)>=d){
			continue;
		}
		for(int j=0;j<(int)b.size();j++){
			double dy=a[i].y-next(b.rbegin(),j)->y;
			if(dy>=d) break;
			d=min(d,abs(a[i]-*next(b.rbegin(),j)));
		}
		b.emplace_back(a[i]);
	}
	return d;
}
//多角形の面積
double area(polygon p){
	double res=0;
	for(int i=0;i<p.size();i++){
		res+=det(p[i],p[(i+1)%p.size()])/2.0;
	}
	return abs(res);
}
//2円の共通部分の面積
double area(circle c1,circle c2){
	double d=abs(c1.c-c2.c);
	if(c1.r+c2.r<=d+EPS){
		return 0;
	}else if(d<=abs(c1.r-c2.r)){
		double r=min(c1.r,c2.r);
		return pi*r*r;
	}
	double rc=(d*d+c1.r*c1.r-c2.r*c2.r)/(2*d);
	double th=acos(rc/c1.r);
	double ph=acos((d-rc)/c2.r);
	return c1.r*c1.r*th+c2.r*c2.r*ph-d*c1.r*sin(th);
}
//多角形と円の共通部分の面積
double area(polygon ps,circle c){
	if(ps.size()<3u){
		return 0;
	}
	function<double(circle,point,point)> dfs=[&](circle c,point a,point b){
		point va=c.c-a,vb=c.c-b;
		double f=det(va,vb),res=0;
		if(equal(f,0.0)){
			return res;
		}else if(max(abs(va),abs(vb))<c.r+EPS){
			return f;
		}
		point d(a.x*b.x+a.y*b.y,a.x*b.y-a.y*b.x);
		if(getDistanceSP(segment(a,b),c.c)>c.r-EPS){
			return c.r*c.r*atan2(d.y,d.x);
		}
		auto u=getCrossPointCS(c,segment(a,b));
		if(u.empty()){
			return res;
		}else if(u.size()>1u&&dot(u[1]-u[0],a-u[0])>0){
			swap(u[0],u[1]);
		}
		u.emplace(u.begin(),a);
		u.emplace_back(b);
		for(int i=1;i<u.size();i++){
			res+=dfs(c,u[i-1],u[i]);
		}
		return res;
	};
	double res=0;
	for(int i=0;i<ps.size();i++){
		res+=dfs(c,ps[i],ps[(i+1)%ps.size()]);
	}
	return res/2;
}
//2点2点を通る直線の垂直二等分線`
line bisector(point p1,point p2){
	circle c1=circle(p1,abs(p1-p2)),c2=circle(p2,abs(p1-p2));
	polygon p=getCrossPointCC(c1,c2);
	if(det(p2-p1,p[0]-p1)>0){
		swap(p[0],p[1]);
	}
	return line(p[0],p[1]);
}
//わからん
Vector translate(Vector v,double theta){
	point res;
	res.x=cos(theta)*v.x-sin(theta)*v.y;
	res.y=sin(theta)*v.x+cos(theta)*v.y;
	return res;
}
//わからん
vector<line> corner(line l1,line l2){
	vector<line> res;
	if(isParallel(l1,l2)){
		double d=getDistanceLP(l1,l2.p1)/2.0;
		point v1=l1.p2-l1.p1;
		v1=v1/v1.abs()*d;
		point p=l2.p1+translate(v1,90.0*(pi/180.0));
		double d1=getDistanceLP(l1,p);
		double d2=getDistanceLP(l2,p);
		if(abs(d1-d2)>d){
			p=l2.p1+translate(v1,-90.0*(pi/180.0));
		}
		res.push_back(line(p,p+v1));
	}else{
		point p=getCrossPointLL(l1,l2);
		point v1=l1.p2-l1.p1,v2=l2.p2-l2.p1;
		v1=v1/v1.abs();
		v2=v2/v2.abs();
		res.push_back(line(p,p+(v1+v2)));
		res.push_back(line(p,p+translate(v1+v2,90.0*(pi/180.0))));
	}
	return res;
}
//わからん
polygon tangent(circle c1,point p2){
	circle c2=circle(p2,sqrt(norm(c1.c-p2)-c1.r*c1.r));
	polygon p=getCrossPointCC(c1,c2);
	sort(p.begin(),p.end());
	return p;
}
//わからん
vector<line> tangent(circle c1,circle c2){
	vector<line> ls;
	if(c1.r<c2.r){
		swap(c1,c2);
	}
	double g=norm(c1.c-c2.c);
	if(equal(g,0)){
		return ls;
	}
	point u=(c2.c-c1.c)/sqrt(g);
	point v=orth(u);
	for(int s=1;s>=-1;s-=2){
		double h=(c1.r+s*c2.r)/sqrt(g);
		if(equal(1-h*h,0)){
			ls.emplace_back(c1.c+u*c1.r,c1.c+(u+v)*c1.r);
		}else if(1-h*h>0){
			point uu=u*h,vv=v*sqrt(1-h*h);
			ls.emplace_back(c1.c+(uu+vv)*c1.r,c2.c-(uu+vv)*c2.r*s);
			ls.emplace_back(c1.c+(uu-vv)*c1.r,c2.c-(uu-vv)*c2.r*s);
		}
	}
	return ls;
}
//x軸またはy軸に平行な線分集合の交点の数
int manhattanIntersection(vector<line> ss,const int inf=2147483647){
	const int BTM = 0;
	const int LFT = 1;
	const int RGH = 2;
	const int TOP = 3;
	int n=ss.size();
	vector<EndPoint> ep;
	for(int i=0;i<n;i++){
		if(ss[i].p1.y==ss[i].p2.y){
			if(ss[i].p1.x>ss[i].p2.x){
				swap(ss[i].p1,ss[i].p2);
			}
			ep.emplace_back(ss[i].p1,i,LFT);
			ep.emplace_back(ss[i].p2,i,RGH);
		}else{
			if(ss[i].p1.y>ss[i].p2.y){
				swap(ss[i].p1,ss[i].p2);
			}
			ep.emplace_back(ss[i].p1,i,BTM);
			ep.emplace_back(ss[i].p2,i,TOP);
		}
	}
	sort(ep.begin(),ep.end());
	set<int> bt;
	bt.insert(inf);
	int cnt=0;
	for(int i=0;i<n*2;i++){
		if(ep[i].st==TOP){
			bt.erase(ep[i].p.x);
		}else if(ep[i].st==BTM){
			bt.emplace(ep[i].p.x);
		}else if(ep[i].st==LFT){
			auto b=bt.lower_bound(ss[ep[i].seg].p1.x);
			auto e=bt.upper_bound(ss[ep[i].seg].p2.x);
			cnt+=distance(b,e);
		}
	}
	return cnt;
}
//直線(p1,p2)と点pから降ろした垂線との交点を求める
//https://onlinejudge.u-aizu.ac.jp/status/users/nii/submissions/1/CGL_1_A/judge/3148053/C++14
void AOJ_CGL1A(){
	point p1,p2;
	cin>>p1>>p2;
	int q;
	cin>>q;
	while(q--){
		point p;
		cin>>p;
		cout<<project(line(p1,p2),p)<<endl;
	}
}
//直線(p1,p2)に対して点pと対象となる交点を求める
//https://onlinejudge.u-aizu.ac.jp/status/users/nii/submissions/1/CGL_1_B/judge/3148065/C++14
void AOJ_CGL1B(){
	point p1,p2;
	cin>>p1>>p2;
	int q;
	cin>>q;
	while(q--){
		point p;
		cin>>p;
		cout<<reflect(line(p1,p2),p)<<endl;
	}
}
//3点p0,p1,p2の状態を求める
//https://onlinejudge.u-aizu.ac.jp/status/users/nii/submissions/1/CGL_1_C/judge/3148083/C++14
void AOJ_CGL1C(){
	point p0,p1;
	cin>>p0>>p1;
	int q;
	cin>>q;
	while(q--){
		point p2;
		cin>>p2;
		int t=ccw(p0,p1,p2);
		if(t==CCW_COUNTER_CLOCKWISE){
			//p0,p1,p2が反時計回り
			cout<<"COUNTER_CLOCKWISE"<<endl;
		}else if(t==CCW_CLOCKWISE){
			//p0,p1,p2が時計回り
			cout<<"CLOCKWISE"<<endl;
		}else if(t==CCW_ONLINE_BACK){
			//p2,p0,p1がこの順で同一直線上
			cout<<"ONLINE_BACK"<<endl;
		}else if(t==CCW_ONLINE_FRONT){
			//p0,p1,p2がこの順で同一直線上
			cout<<"ONLINE_FRONT"<<endl;
		}else{
			//線分p0-p1上にp2
			cout<<"ON_SEGMENT"<<endl;
		}
	}
}
//2直線の状態を求める
//https://onlinejudge.u-aizu.ac.jp/status/users/nii/submissions/1/CGL_2_A/judge/3148097/C++14
void AOJ_CGL2A(){
	int q;
	cin>>q;
	while(q--){
		point p0,p1,p2,p3;
		cin>>p0>>p1>>p2>>p3;
		if(isParallel(line(p0,p1),line(p2,p3))){
			cout<<2<<endl;
		}else if(isOrthogonal(line(p0,p1),line(p2,p3))){
			cout<<1<<endl;
		}else{
			cout<<0<<endl;
		}
	}
}
//2線分の交差判定
//https://onlinejudge.u-aizu.ac.jp/status/users/nii/submissions/1/CGL_2_B/judge/3148101/C++14
void AOJ_CGL2B(){
	int q;
	cin>>q;
	while(q--){
		point p0,p1,p2,p3;
		cin>>p0>>p1>>p2>>p3;
		cout<<intersectSS(line(p0,p1),line(p2,p3))<<endl;
	}
}
//2線分の交点を求める
//https://onlinejudge.u-aizu.ac.jp/status/users/nii/submissions/1/CGL_2_C/judge/3148118/C++14
void AOJ_CGL2C(){
	int q;
	cin>>q;
	while(q--){
		point p0,p1,p2,p3;
		cin>>p0>>p1>>p2>>p3;
		cout<<getCrossPointSS(line(p0,p1),line(p2,p3))<<endl;
	}
}
//2線分の距離を求める
//https://onlinejudge.u-aizu.ac.jp/status/users/nii/submissions/1/CGL_2_D/judge/3148126/C++14
void AOJ_CGL2D(){
	int q;
	cin>>q;
	while(q--){
		point p0,p1,p2,p3;
		cin>>p0>>p1>>p2>>p3;
		cout<<fixed<<setprecision(12)<<getDistanceSS(line(p0,p1),line(p2,p3))<<endl;
	}
}
//多角形pの面積を求める
//https://onlinejudge.u-aizu.ac.jp/status/users/nii/submissions/2/CGL_3_A/judge/3148142/C++14
void AOJ_CGL3A(){
	int n;
	cin>>n;
	polygon p(n);
	for(int i=0;i<n;i++){
		cin>>p[i];
	}
	cout<<fixed<<setprecision(12)<<area(p)<<endl;
}
//多角形pは凸多角形か判定する
//https://onlinejudge.u-aizu.ac.jp/status/users/nii/submissions/2/CGL_3_B/judge/3148147/C++14
void AOJ_CGL3B(){
	int n;
	cin>>n;
	polygon p(n);
	for(int i=0;i<n;i++){
		cin>>p[i];
	}
	cout<<isConvex(p)<<endl;
}
//多角形pと点rの状態を求める
//2:in 1:on 0:out
void AOJ_CGL3C(){
	int n;
	cin>>n;
	polygon p(n);
	for(int i=0;i<n;i++){
		cin>>p[i];
	}
	int q;
	cin>>q;
	while(q--){
		point r;
		cin>>r;
		cout<<isContain(p,r)<<endl;
	}
}
//凸包
//一番下の一番左から反時計回りに出力
//https://onlinejudge.u-aizu.ac.jp/status/users/nii/submissions/2/CGL_4_A/judge/3148157/C++14
void AOJ_CGL4A(){
	int n;
	cin>>n;
	polygon p(n);
	for(int i=0;i<n;i++){
		cin>>p[i];
	}
	polygon q=convex_hull(p);
	cout<<q.size()<<endl;
	for(int i=0;i<q.size();i++){
		cout<<q[i].x<<" "<<q[i].y<<endl;
	}
}
//凸多角形の直径
//凸多角形pの最遠頂点対間距離を求める
//https://onlinejudge.u-aizu.ac.jp/status/users/nii/submissions/2/CGL_4_B/judge/3148161/C++14
void AOJ_CGL4B(){
	int n;
	cin>>n;
	polygon p(n);
	for(int i=0;i<n;i++){
		cin>>p[i];
	}
	cout<<fixed<<setprecision(12)<<diameter(p)<<endl;
}
//凸多角形を直線p1-p2で切断しその左側の面積を求め
//https://onlinejudge.u-aizu.ac.jp/status/users/nii/submissions/2/CGL_4_C/judge/3148170/C++14
void AOJ_CGL4C(){
	int n;
	cin>>n;
	polygon g(n);
	for(int i=0;i<n;i++){
		cin>>g[i];
	}
	polygon p=andrewScan(g);
	int q;
	cin>>q;
	while(q--){
		line l;
		cin>>l.p1>>l.p2;
		cout<<fixed<<setprecision(12)<<area(convexCut(p,l))<<endl;
	}
}
//平面上の2点の最近頂点対間距離を求める
//https://onlinejudge.u-aizu.ac.jp/status/users/nii/submissions/2/CGL_5_A/judge/3148176/C++14
void AOJ_CGL5A(){
	int n;
	cin>>n;
	polygon p(n);
	for(int i=0;i<n;i++){
		cin>>p[i];
	}
	cout<<fixed<<setprecision(12)<<closest_pair(p)<<endl;
}
//x軸またはy軸に平行な線分集合の交点の数を求める
//https://onlinejudge.u-aizu.ac.jp/status/users/nii/submissions/1/CGL_6_A/judge/3148179/C++14
void AOJ_CGL6A(){
	int n;
	cin>>n;
	vector<line> ss(n);
	for(int i=0;i<n;i++){
		cin>>ss[i];
	}
	cout<<manhattanIntersection(ss,2147483647)<<endl;
}
//2円の状態を求める
//https://onlinejudge.u-aizu.ac.jp/status/users/nii/submissions/1/CGL_7_A/judge/3148191/C++14
void AOJ_CGL7A(){
	circle c1,c2;
	cin>>c1>>c2;
	cout<<intersectCC(c1,c2)<<endl;
}
//円cと直線lの交点を求める
//https://onlinejudge.u-aizu.ac.jp/status/users/nii/submissions/1/CGL_7_D/judge/3148196/C++14
void AOJ_CGL7D(){
	circle c;
	int q;
	cin>>c>>q;
	while(q--){
		line l;
		cin>>l;
		auto pp=getCrossPointCL(c,l);
		if(pp.size()==1u){
			pp.emplace_back(pp[0]);
		}
		if(pp[1]<pp[0]){
			swap(pp[0],pp[1]);
		}
		cout<<pp[0]<<" "<<pp[1]<<endl;
	}
}
//2円の交点を求める
//https://onlinejudge.u-aizu.ac.jp/status/users/nii/submissions/1/CGL_7_E/judge/3148198/C++14
void AOJ_CGL7E(){
	circle c1,c2;
	cin>>c1>>c2;
	auto pp=getCrossPointCC(c1,c2);
	if(pp.size()==1u){
		pp.emplace_back(pp[0]);
	}
	if(pp[1]<pp[0]){
		swap(pp[0],pp[1]);
	}
	cout<<pp[0]<<" "<<pp[1]<<endl;
}
//点pを通る円cの接戦と円cとの接点を求める
//https://onlinejudge.u-aizu.ac.jp/status/users/nii/submissions/1/CGL_7_F/judge/3148207/C++14
void AOJ_CGL7F(){
	point p;
	circle c;
	cin>>p>>c;
	auto pp=tangent(c,p);
	for(auto p:pp){
		cout<<p<<endl;
	}
}
//2円の共通接線の円c1における接点を求める
//https://onlinejudge.u-aizu.ac.jp/status/users/nii/submissions/1/CGL_7_G/judge/3148211/C++14
void AOJ_CGL7G(){
	circle c1,c2;
	cin>>c1>>c2;
	auto ls=tangent(c1,c2);
	polygon ps;
	for(auto l:ls){
		ps.emplace_back(getCrossPointCL(c1,l)[0]);
	}
	sort(ps.begin(),ps.end());
	for(auto p:ps){
		cout<<p<<endl;
	}
}
//円と多角形の共通部分の面積を求める
//https://onlinejudge.u-aizu.ac.jp/status/users/nii/submissions/1/CGL_7_H/judge/3148224/C++14
void AOJ_CGL7H(){
	int n;
	double r;
	cin>>n>>r;
	circle c(point(0,0),r);
	polygon ps(n);
	for(int i=0;i<n;i++){
		cin>>ps[i];
	}
	cout<<fixed<<setprecision(12)<<area(ps,c)<<endl;
}
//平面上の直線によって平面はいくつの領域に分割されますか
//https://beta.atcoder.jp/contests/joisc2007/submissions/3237997・・
void JOI_2007_line(){
	int n;
	cin>>n;
	vector<line> ls;
	for(int i=0;i<n;i++){
		line l;
		cin>>l.p1>>l.p2;
		bool f=true;
		for(int j=0;j<ls.size();j++){
			if(isParallel(l,ls[j])&&isSame(l,ls[j])){
				f=false;
				break;
			}
		}
		if(f){
			ls.push_back(l);
		}
	}
	n=ls.size();
	int ans=1;
	for(int i=0;i<n;i++){
		set<point> S;
		for(int j=i+1;j<n;j++){
			if(!isParallel(ls[i],ls[j])&&S.find(getCrossPointLL(ls[i],ls[j]))==S.end()){
				S.insert(getCrossPointLL(ls[i],ls[j]));
				ans++;
			}
		}
		ans++;
	}
	cout<<ans<<endl;
}
//十分に広い平面上に穴がいくつかあって、その平面上のどこかにすぬけ君を置いて一番近いところに落ちるのだが、それぞれの穴に落ちる確率を求める
//https://beta.atcoder.jp/contests/agc021/submissions/3249221
void AGC021_B(){
	int n;
	cin>>n;
	polygon q(n);
	map<point,int> M;
	for(int i=0;i<n;i++){
		cin>>q[i];
		M[q[i]]=i;
	}
	//
	double ans[100];
	fill(ans,ans+n,0);
	polygon p=convex_hull(q);
	if(p.size()==2){
		ans[M[p[0]]]=0.5;
		ans[M[p[1]]]=0.5;
	}else{
		int nn=p.size();
		for(int i=0;i<nn;i++){
			line l0=bisector(p[(i+nn-1)%nn],p[i]);
			line l1=bisector(p[i],p[(i+1)%nn]);
			Vector v0=l0.p1-l0.p2;
			Vector v1=l1.p1-l1.p2;
			double res=acos(max(-1.0,min(1.0,(dot(v0,v1)/(abs(v0)*abs(v1))))))/(2*pi);
			ans[M[p[i]]]+=res;
		}
	}
	//
	for(int i=0;i<n;i++){
		cout<<fixed<<setprecision(12)<<ans[i]<<endl;
	}
}
//始点終点とそれとは別に多角形が与えられ、多角形の一部を通るルートの最小値
//凸包するか三分探索をしている
//https://onlinejudge.u-aizu.ac.jp/status/users/nii/submissions/1/0375/judge/3237389/C++14
void PCK2017(){
	point s,g;
	int N;
	polygon lake;
	cin>>s>>g;
	cin>>N;
	lake.resize(N);
	for(int i=0;i<N;i++){
		cin>>lake[i];
	}
	segment sg;
	sg.p1=s;sg.p2=g;
	if(intersectPS(lake,sg)){
		lake.push_back(s);
		lake.push_back(g);
		polygon all=convex_hull(lake);
		int l=all.size();
		int sidx=-1,gidx=-1;
		for(int i=0;i<l;i++){
			if(all[i]==s){
				sidx=i;
			}else if(all[i]==g){
				gidx=i;
			}
			if(sidx!=-1&&gidx!=-1){
				break;
			}
		}
		if(sidx>gidx){
			swap(sidx,gidx);
		}
		vector<pair<int,int>> a,b;
		for(int i=sidx;i<gidx;i++){
			a.push_back(make_pair(i,i+1));
		}
		for(int i=sidx;i>0;i--){
			b.push_back(make_pair(i,i-1));
		}
		b.push_back(make_pair(0,l-1));
		for(int i=l-1;i>gidx;i--){
			b.push_back(make_pair(i,i-1));
		}
		double aa=0,bb=0;
		for(int i=0;i<a.size();i++){
			aa+=abs(all[a[i].first]-all[a[i].second]);
		}
		for(int i=0;i<b.size();i++){
			bb+=abs(all[b[i].first]-all[b[i].second]);
		}
		cout<<fixed<<setprecision(12)<<min(aa,bb)<<endl;
	}else{
		lake.push_back(lake[0]);
		double ans=1e9+7;
		for(int i=0;i<lake.size()-1;i++){
			point p=lake[i],q=lake[i+1];
			for(int j=0;j<86;j++){
				point ppq=(p*2+q)/3,pqq=(p+q*2)/3;
				if((abs(ppq-s)+abs(ppq-g))-(abs(pqq-s)+abs(pqq-g))>EPS){
					p=ppq;
				}else{
					q=pqq;
				}
			}
			point pq=(p+q)/2;
			ans=min(ans,abs(pq-s)+abs(pq-g));
		}
		cout<<fixed<<setprecision(12)<<ans<<endl;
	}
}
int main(){
	int n;
	cin>>n;
	if(n==2){
		point a,b;
		cin>>a>>b;
		cout<<fixed<<setprecision(12)<<abs(a-b)/2<<endl;
		return 0;
	}
	polygon p(n);
	for(int i=0;i<n;i++){
		cin>>p[i];
	}
//	polygon q=convex_hull(p);
//	int m=q.size();
	double ans=1e9+7;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			for(int k=j+1;k<n;k++){
				double a=p[i].x;
				double b=p[i].y;
				double c=p[j].x;
				double d=p[j].y;
				double e=p[k].x;
				double f=p[k].y;
				double py=((e-a)*(a*a+b*b-c*c-d*d)-(c-a)*(a*a+b*b-e*e-f*f))/(2*(e-a)*(b-d)-2*(c-a)*(b-f));
				double px;
				if(c-a!=0){
					px=(2*(b-d)*py-a*a-b*b+c*c+d*d)/(2*(c-a));
				}else{
					px=(2*(b-f)*py-a*a-b*b+e*e+f*f)/(2*(e-a));
				}
				point O;
				O.x=px;
				O.y=py;
				bool ok=true;
				for(int l=0;l<n;l++){
					if(l==i||l==j||l==k){
						continue;
					}else if(abs(p[l]-O)>abs(p[i]-O)){
						ok=false;
					}
				}
				if(ok){
					ans=min(ans,abs(p[i]-O));
				}
			}
		}
	}
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(abs(p[i]-p[j])<2*ans){
				point m=(p[i]+p[j])/2;
				bool ok=true;
				for(int k=0;k<n;k++){
					if(k==i||k==j){
						continue;
					}else{
						if(abs(m-p[k])>abs(m-p[i])){
							ok=false;
						}
					}
				}
				if(ok){
					ans=abs(m-p[i]);
				}
			}
		}
	}
	cout<<fixed<<setprecision(12)<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256