#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;
}
//
double macos(double x){
	return acos(max(-1.0,min(1.0,x)));
}
double ans[100];
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;
	}
	//
	polygon p=convex_hull(q);
	if(p.size()==2){
		ans[M[p[0]]]=0.5;
		ans[M[p[1]]]=0.5;
	}else{
		for(int i=0;i<p.size();i++){
			int pre=(i+p.size()-1)%p.size(),now=i,nex=(i+1)%p.size();
			line l0=bisector(p[pre],p[now]);
			line l1=bisector(p[now],p[nex]);
			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[now]]]+=res;
		}
	}
	//
	for(int i=0;i<n;i++){
		cout<<fixed<<setprecision(12)<<ans[i]<<endl;
	}
}
int main(){
	AGC021_B();
	return 0;
}


Measured memory_bytes: 256