using namespace std;
const int maxn=1010;//一般计算几何数字不会太大
const double pi=acos(-1.0);
const double eps=1e-8;
int sgn(double x){//double而决定的0
if(fabs(x)<eps)return 0;
else return x<0?-1:1;
}
int Dcmp(double x,double y){//double而决定的比较大小
if(fabs(x-y)<eps)return 0;
return 1;
}
struct Point{//点的基操
double x,y;
Point(){}
Point(double x,double y):x(x),y(y){}
Point operator + (Point B){return Point(x+B.x,y+B.y);}
Point operator - (Point B){return Point(x-B.x,y-B.y);}
Point operator * (double k){return Point(x*k,y*k);}
Point operator / (double k){return Point(x/k,y/k);}
bool operator == (Point B){return sgn(x-B.x)==0&&sgn(y-B.y)==0;}
bool operator < (Point B){return sgn(x-B.x<0)||(sgn(x-B.x)==0&&sgn(y-B.y)<0);}
};
typedef Point Vector;//定义向量
double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}
double Len(Vector A){return sqrt(Dot(A,A));}
double Len_2(Vector A){return Dot(A,A);}
double Angle(Vector A,Vector B){return acos(Dot(A,B)/Len(A)/Len(B));}
double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}
double Area2(Point A,Point B,Point C){return Cross(B-A,C-A);}
double Dist(Point A,Point B){return hypot(A.x-B.x,A.y-B.y);}
Vector Normal(Vector A){return Vector(-A.y/Len(A),A.x/Len(A));}
bool Parallel(Vector A,Vector B){return sgn(Cross(A,B))==0;}
Vector Rotate(Vector A,double rad){return Vector(A.x*cos(rad)-A.y*cos(rad),A.x*sin(rad)+A.y*sin(rad));}
struct Line{
Point p1,p2;
Line(){};
Line(Point p1,Point p2):p1(p1),p2(p2){}
Line(Point p,double angle){
p1=p;
if(sgn(angle-pi/2)==0){p2=p1+Point(0,1);}
else {p2=(p1+Point(1,tan(angle)));}
}
Line(double a,double b,double c){
if(sgn(a)==0){
p1=Point(0,-c/b);
p2=Point(1,-c/b);
}
else if(sgn(b)==0){
p1=Point(-c/a,0);
p2=Point(-c/a,1);
}
else{
p1=Point(0,-c/a);
p2=Point(1,(-c-a)/b);
}
}
};
typedef Line Segment;
double Line_angle(Line v){
double k=atan2(v.p2.y-v.p1.y,v.p2.x-v.p1.x);
if(sgn(k)<0)k+=pi;if(sgn(k-pi)==0)k-=pi;return k;
}
int Point_line_relation(Point p,Line v){
int c=sgn(Cross(p-v.p1,v.p2-v.p1));
if(c<0) return 1;//left
if(c>0)return -1;//right
return 0;//on
}
bool Point_on_seg(Point p,Line v){return (sgn(Cross(p-v.p1,v.p2-v.p1))==0&&sgn(Dot(p-v.p1,v.p2-v.p1))<=0);}
int Line_relation(Line v1,Line v2){
if(sgn(Cross(v1.p2-v1.p1,v2.p2-v2.p1))==0){
if(Point_line_relation(v1.p1,v2)==0)return 1;//重合
else return 0;//平行
}
return -1;//相交
}
double Dis_point_line(Point p,Line v){return fabs(Cross(p-v.p1,v.p2-v.p1));}
Point Point_line_proj(Point p,Line v){return (v.p1+(v.p2-v.p1)*(Dot(v.p2-v.p1,p-v.p1)/Len_2(v.p2-v.p1)));}
Point Point_line_symmetry(Point p,Line v){
Point q=Point_line_proj(p,v);
return Point(2*q.x-p.x,2*q.y-p.y);
}
double Dis_point_seg(Point p,Segment v){
if(sgn(Dot(p-v.p1,v.p2-v.p1))<0||sgn(Dot(p-v.p2,v.p1-v.p2))<0)
return min(Dist(p,v.p1),Dist(p,v.p2));
return Dis_point_line(p,v);
}
Point Cross_point(Point a,Point b,Point c,Point d){
double s1=Cross(b-a,c-a);
double s2=Cross(b-a,d-a);
return Point(c.x*s2-d.x*s1,c.y*s2-d.y*s1)/(s2-s1);
}
bool Corss_segment(Point a,Point b,Point c,Point d){
double c1=Cross(b-a,c-a);double c2=Cross(b-a,d-a);
double d1=Cross(d-c,a-c);double d2=Cross(d-c,b-c);
return sgn(c1)*sgn(c2)<0&&sgn(d1)*sgn(d2)<0;
}
struct Polygon{
int n;
Point p[maxn];
Line v[maxn];
};
int Point_in_polygon(Point pt,Point *p,int n){
for(int i=0;i<n;i++){
if(p[i]==pt)return 3;//点上
}
for(int i=0;i<n;i++){
Line v=Line(p[i],p[(i+1)%n]);
if(Point_on_seg(pt,v))return 2;//边上
}
int num=0;
for(int i=0;i<n;i++){
int j=(i+1)%n;
int c=sgn(Cross(pt-p[j],p[i]-p[j]));
int u=sgn(p[i].y-pt.y);
int v=sgn(p[j].y-pt.y);
if(c>0&&u<0&&v>=0)num++;
if(c<0&&u>0&&v<0)num--;
return num!=0;//1内0外
}
}
double Polygon_area(Point *p,int n){
double area=0;
for(int i=0;i<n;i++)area+=Cross(p[i],p[(i+1)%n]);
return area/2;
}
Point Polygon_center(Point *p,int n){
Point ans(0,0);
if(Polygon_area(p,n)==0)return ans;
for(int i=0;i<n;i++)ans=ans+((p[i]+p[(i+1)%n])*Cross(p[i],p[(i+1)%n]));
return ans/Polygon_area(p,n)/6;
}
int Convex_hull(Point *p,int n,Point *ch){
sort(p,p+n);n=unique(p,p+n)-p;int v=0;
for(int i=0;i<n;i++){
while(v>1&&sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-2]))<=0)v--;
ch[v++]=p[i];
}
int j=v;
for(int i=n-2;i>=0;i--){
while(v>j&&sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-2]))<=0)v--;
ch[v++]=p[i];
}
if(n>1)v--;
return v;
}
struct Circle{
Point c;double r;
Circle(){};
Circle(Point c,double r):c(c),r(r){}
Circle(double x,double y,double _r){c=Point(x,y);r=_r;}
};
int Point_circle_relation(Point p,Circle C){
double dst=Dist(p,C.c);
if(sgn(dst-C.r)<0)return 0;
if(sgn(dst-C.r)==0)return 1;
return -1;
}
int Line_circle_relation(Segment v,Circle C){
double dst=Dis_point_line(C.c,v);
if(sgn(dst-C.r)<0)return 1;
if(sgn(dst-C.r)==0)return 0;
return -1;
}
int Line_cross_circle(Line v,Circle C,Point &pa,Point &pb){
if(Line_circle_relation(v,C)==-1)return 0;
Point q=Point_line_proj(C.c,v);
double d=Dis_point_line(C.c,v);
double k=sqrt(C.r*C.r-d*d);
if(sgn(k)==0){
pa=q;pb=q;return 1;
}
Point n=(v.p2-v.p1)/Len(v.p2-v.p1);
pa=q+n*k;pb=q-n*k;
return 2;