typedef double db;
const db eps=1e-6;
//點(diǎn).向量
struct point
{
db x,y,len2,angle;
point() {}
point(db _x,db _y){set(_x,_y);}
void set(db _x,db _y)
{
x=_x,y=_y;
len2=x*x+y*y;
angle=atan2(y,x);
}
void print(){printf("(%.6f,%.6f)",(double)x,(double)y);}
void println(){print();puts("");}
//逆時(shí)針旋轉(zhuǎn)
point rotate(db alpha)
{
db _x=x*cos(alpha)-y*sin(alpha);
db _y=x*sin(alpha)+y*cos(alpha);
return point(_x,_y);
}
//向量夾角
db get_angle(point &p)
{
return acos((*this)*p/length()/p.length());
}
db length(){return sqrt(len2);}
point operator+(const point &p){return point(x+p.x,y+p.y);}
point operator-(const point &p){return point(x-p.x,y-p.y);}
point operator*(const db k){return point(k*x,k*y);}
point operator/(const db k){return point(x/k,y/k);}
db operator*(const point &p){return x*p.x+y*p.y;}
db operator^(const point &p){return x*p.y-y*p.x;}
bool operator==(const point &p){return fabs(x-p.x)<eps && fabs(y-p.y)<eps;}
};
//線
struct line
{
point st,ed,vec;
db len2,angle;
line() {}
line(point s,point e) {set(s,e);}
void set(point s,point e)
{
st=s,ed=e,vec=e-s;
len2=vec.len2;
angle=atan2(vec.y,vec.x);
}
//延長k倍
line operator*(db k){return line(st,st+vec*k);}
//靠近st的1/k分點(diǎn)
point operator/(db k){return st+vec/k;}
db length(){return sqrt(len2);}
//點(diǎn)在直線左側(cè)
bool on_left(point p){return (vec^(p-st))>eps;}
//點(diǎn)在直線上
bool on_line(point p){return fabs(vec^(p-st))<eps;}
//點(diǎn)在線段上
bool on_segment(point p)
{
if(p.x+eps<min(st.x,ed.x) || p.x-eps>max(st.x,ed.x))
return false;
if(p.y+eps<min(st.y,ed.y) || p.y-eps>max(st.y,ed.y))
return false;
return on_line(p);
}
//直線平行
bool parallel(line l){return fabs(vec^l.vec)<eps;}
//直線重合
bool coincidence(line l){return on_line(l.st) && on_line(l.ed);}
//直線交點(diǎn)
point get_intersection(line l)
{
db x1=st.x,y1=st.y,x2=ed.x,y2=ed.y;
db x3=l.st.x,y3=l.st.y,x4=l.ed.x,y4=l.ed.y;
db k1=(x4-x3)*(y2-y1),k2=(x2-x1)*(y4-y3);
db x=(k1*x1-k2*x3+(y3-y1)*(x2-x1)*(x4-x3))/(k1-k2);
db y=(k2*y1-k1*y3+(x3-x1)*(y2-y1)*(y4-y3))/(k2-k1);
return point(x,y);
}
//線段相交
bool segment_intersection(line l)
{
if(coincidence(l))
return on_segment(l.st) || on_segment(l.ed)
|| l.on_segment(st) || l.on_segment(ed);
return ((l.st-st)^vec)*((l.ed-st)^vec)<=0
&& ((st-l.st)^l.vec)*((ed-l.st)^l.vec)<=0;
}
//線段中垂線
line vertical_bisector()
{
db x1=st.x,y1=st.y,x2=ed.x,y2=ed.y;
db xm=(x1+x2)/2.0,ym=(y1+y2)/2.0;
return line(point(xm+ym-y1,ym-xm+x1),point(xm-ym+y1,ym+xm-x1));
}
//直線旋轉(zhuǎn)
line rotate(db alpha)
{
point v=vec.rotate(alpha);
return line(st,st+v);
}
//垂線
line vertical(point p)
{
point l(vec.y,-vec.x);
l=l*(distance(p)/l.length());
if(on_line(p+l))return line(p,p+l);
else return line(p,p-l);
}
//直線夾角
db get_angle(line l){return vec.get_angle(l.vec);}
//點(diǎn)到直線的距離
db distance(point p){return fabs((p-st)^(p-ed))/(length());}
//中點(diǎn)
point midpoint(){return point((st.x+ed.x)/2,(st.y+ed.y)/2);}
void print(){st.print();putchar('-');ed.print();}
void println(){print();puts("");}
};
//三角形
struct triangle
{
point v[4];line e[4];
triangle(point p1,point p2,point p3)
{
point p[4]={point(),p1,p2,p3};
set(p);
}
triangle(point p[]) {set(p);}
//構(gòu)造逆時(shí)針三角形(注意特判三點(diǎn)共線)
void set(point p[])
{
for(int i=1;i<=3;++i)v[i]=p[i];
if(!line(v[1],v[2]).on_left(v[3]))
swap(v[2],v[3]);
for(int i=1;i<=2;++i)e[i].set(v[i],v[i+1]);
e[3].set(v[3],v[1]);
}
bool inside(point p)
{
return e[1].on_left(p)==e[2].on_left(p)
&& e[1].on_left(p)==e[3].on_left(p);
}
//重心(中線交點(diǎn))
point gravity(){return (v[1]+v[2]+v[3])/3;}
//外心
point circum_center()
{
line l1=e[1].vertical_bisector();
line l2=e[2].vertical_bisector();
return l1.get_intersection(l2);
}
//內(nèi)心
point inscribed_center()
{
db a=e[2].length(),b=e[3].length(),c=e[1].length();
db x=(a*v[1].x+b*v[2].x+c*v[3].x)/(a+b+c);
db y=(a*v[1].y+b*v[2].y+c*v[3].y)/(a+b+c);
return point(x,y);
}
//垂心
point orthocenter()
{
line l1=e[1].vertical(v[3]);
line l2=e[2].vertical(v[1]);
return l1.get_intersection(l2);
}
//周長
db perimeter()
{
db sum=0.0;
for(int i=1;i<=3;++i)sum+=e[i].length();
return sum;
}
//面積
db area(){return fabs((v[3]-v[1])^(v[2]-v[1]))/2;}
void print(){for(int i=1;i<=3;++i){v[i].print();if(i!=3)putchar('-');}}
void println(){print();puts("");}
};
//矩形
struct rectangle
{
point v[5];line e[5];
rectangle(point p1,point p2)
{
point p[5]={point(),point(p1.x,p1.y),point(p1.x,p2.y),
point(p2.x,p1.y),point(p2.x,p2.y)};
set(p);
}
rectangle(point p1,point p2,point p3,point p4)
{
point p[5]={point(),p1,p2,p3,p4};
set(p);
}
rectangle(point p[]) {set(p);}
//構(gòu)造出順時(shí)針或逆時(shí)針的矩形(注意特判四點(diǎn)共線)
void set(point p[])
{
for(int i=1;i<=4;++i)v[i].set(p[i].x,p[i].y);
if(!line(v[1],v[2]).parallel(line(v[3],v[4])))
swap(v[2],v[3]);
if(!line(v[1],v[4]).parallel(line(v[2],v[3])))
swap(v[3],v[4]);
for(int i=1;i<=3;++i)e[i].set(v[i],v[i+1]);
e[4].set(v[4],v[1]);
}
//點(diǎn)在矩形內(nèi)或矩形上
bool inside(point p)
{
bool flag=true;
for(int i=1;i<=4;++i)
{
if(e[i].on_segment(p))return true;
if(e[i].on_left(p)!=e[1].on_left(p))
flag=false;
}
return flag;
}
bool inside(line l){return inside(l.st) && inside(l.ed);}
bool intersection(line l)
{
for(int i=1;i<=4;++i)
if(e[i].segment_intersection(l))
return true;
return false;
}
void print(){for(int i=1;i<=4;++i){v[i].print();if(i!=4)putchar('-');}}
void println(){print();puts("");}
};
//圓
struct circle
{
point c;db r;
circle() {}
circle(point p,db _r){set(p,_r);}
void set(point p,db _r){c=p,r=_r;}
//外接圓
static circle circum_circle(triangle t)
{
point p=t.circum_center();
return circle(p,line(p,t.v[1]).length());
}
//內(nèi)接圓
static circle inscribed_circle(triangle t)
{
point p=t.inscribed_center();
return circle(p,t.area()*2/t.perimeter());
}
//點(diǎn)在圓內(nèi)或圓上
bool inside(point p){return line(p,c).len2<=r*r;}
void print(){c.print(),printf(" r:%.2f",(double)r);}
void println(){print();puts("");}
};
struct polygon
{
const static int __=1e3+5;
point v[__];int n;
polygon() {}
polygon(point p[],int n)
{
for(int i=1;i<=n;++i)v[i]=p[i];
v[0]=p[n],v[n+1]=p[1];
this->n=n;
}
db area()
{
db res=0.0;
for(int i=1;i<=n;++i)
res+=v[i]^v[i+1];
return fabs(res)/2;
}
};
球體積交 && 球體積并
const ld pi=acos(-1);
ld pow2(ld x){return x*x;}
ld pow3(ld x){return x*x*x;}
ld dis(ld x1,ld y1,ld z1,ld x2,ld y2,ld z2)
{
return pow2(x1-x2)+pow2(y1-y2)+pow2(z1-z2);
}
ld cos(ld a,ld b,ld c){return (b*b+c*c-a*a)/(2*b*c);}
ld cap(ld r,ld h){return pi*(r*3-h)*h*h/3;}
//2球體積交
ld sphere_intersect(ld x1,ld y1,ld z1,ld r1,ld x2,ld y2,ld z2,ld r2)
{
ld d=dis(x1,y1,z1,x2,y2,z2);
//相離
if(d>=pow2(r1+r2))return 0;
//包含
if(d<=pow2(r1-r2))return pow3(min(r1,r2))*4*pi/3;
//相交
ld h1=r1-r1*cos(r2,r1,sqrt(d)),h2=r2-r2*cos(r1,r2,sqrt(d));
return cap(r1,h1)+cap(r2,h2);
}
//2球體積并
ld sphere_union(ld x1,ld y1,ld z1,ld r1,ld x2,ld y2,ld z2,ld r2)
{
ld d=dis(x1,y1,z1,x2,y2,z2);
//相離
if(d>=pow2(r1+r2))return (pow3(r1)+pow3(r2))*4*pi/3;
//包含
if(d<=pow2(r1-r2))return pow3(max(r1,r2))*4*pi/3;
//相交
ld h1=r1+r1*cos(r2,r1,sqrt(d)),h2=r2+r2*cos(r1,r2,sqrt(d));
return cap(r1,h1)+cap(r2,h2);
}
