【板子】常见几何

几个知识点：

直线的斜率可以通过 c++函数atan2(Δy,Δx) 求出，其返回的是弧度，即当斜率为90°时
atan2(90°)=1.57

c++的sin(x),cos(x)这些函数都是使用弧度制的

3.点 $图片说明$ 顺时针旋转θ角度后的新坐标

$x=(x_{p}-x_{0})cos\theta-(y_{p}-y_{0})sin\theta+x_{0}$
$图片说明$
//没有凸包

/*------------------ 二维几何 ------------------------------------------------------------------ */

const double eps=1e-8;
const double inf=1e20;
const double pi=acos(-1.0);
const int maxp=1010;//点的个数

int sgn(double x)
{
    if(fabs(x)<eps) return 0;
    if(x<0) return -1;
    else return 1;
}
//判断小数和0是否等于

struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y){x=_x,y=_y;}

    void input(){scanf("%lf%lf",&x,&y);}//输入
    void output(){printf("%.2f %.2f\n", x,y);} //输出

    Point operator -(const Point &b)const {return Point(x-b.x,y-b.y);}
    Point operator+(const Point &b) const{ return Point(x + b.x, y + b.y); }
    Point operator *(const double &k)const{return Point(x*k,y*k);}
    Point operator /(const double &k)const{return Point(x/k,y/k);}
    bool operator ==(Point b)const {return sgn(x-b.x)==0 &&sgn(y-b.y)==0;}
    bool operator <(Point b)const{return sgn(x-b.x)==0?sgn(y-b.y)<0:x<b.x;}


    double operator ^(const Point &b)const{return x*b.y-y*b.x;}
    //叉积

    double operator *(const Point &b)const{return x*b.x+y*b.y;}
    //点积

    double len(){return hypot(x,y);}
    //返回长度

    double len2(){return x*x+y*y;}
    //返回长度的平方

    double distance(Point p){return hypot(x-p.x,y-p.y);}
    //两点之间的距离

    double rad(Point a,Point b){
        Point p=*this;
        return fabs(atan2( fabs((a-p)^(b-p)) , (a-p)^(b-p) ));
    }//求pa,pb之间的夹角

    Point trunc(double r){
        double l=len();
        if(!sgn(l)) return *this;
        r/=l;
        return Point(x*r,y*r);
    }//化为长度为r的向量

    Point rotLeft(){return Point(-y,x);}
    //逆时针旋转90°

    Point rotRight(){return Point(y,-x);}
    //顺时针旋转90°

    Point rotate(Point p,double angle){
        Point v=(*this)-p;
        double c=cos(angle),s=sin(angle);
        return Point(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c);
    }//绕p点逆时针旋转angle
};
typedef Point Vector;
typedef Point point;

double area(Point x,Point y,Point z){
    double xy=x.distance(y);
    double xz=x.distance(z);
    double yz=y.distance(z);

    double d=(xy+xz+yz)/2;//半周长p
    return sqrt(d*(d-xy)*(d-xz)*(d-yz));

}//三角形面积

double area(Point a,Point b,Point c){
    return fabs(a.x*b.y+a.y*c.x+b.x*c.y - a.x*c.y-a.y*b.x-b.y*c.x)/2;
}//三角形面积
/*------------------------直线 ------------------------------------------------------------------ */
struct Line{
    Point s,e;
    Line(){}
    Line(Point _s,Point _e){s=_s;e=_e;}
    bool operator == (Line v){return (s==v.s)&&(e==v.e);}

    Line(Point p,double angle){
        s=p;
        if(sgn(angle-pi/2)==0)
            e=(s+Point(0,1));
        else
            e=(s+Point(1,tan(angle)));
    }//根据一个点和倾斜角确定直线 0<=angle<pi

    Line(double a,double b,double c)
    {
        if(sgn(a)==0){
            s=Point(0,-c/b);
            e=Point(1,-c/b);
        }
        else if(sgn(b)==0){
            s=Point(-c/a,0);
            e=Point(-c/a,1);
        }
        else{
            s = Point(0, -c / b);
            e = Point(1, (-c - a) / b);
        }
    }//求出直线ax+by+c=0;

    void input(){s.input();e.input();}//输入

    //void adjust(){if(e<s) swap(s,e);} //emmm 我不是很喜欢这个

    double length(){return s.distance(e);}
    //求线段长度

    double angle(){
        double k=atan2(e.y-s.y,e.x-s.x);
        if(sgn(k)<0)k+=pi;
        if(sgn(k-pi)==0) k-=pi;
        return k;
    }//返回直线倾斜角 0<=angle<pi


    int relation(Point p){
        int c=sgn((p-s)^(e-s));
        if(c<0) return 1; //点在直线的左侧
        else if(c>0) return 2;//点在直线的右侧
        else return 3;//点在直线上
    }//判断点与直线的关系

    bool point_on_seg(Point p){
        return sgn((p-s)^(e-s))==0 && sgn((p-s)*(p-e))<=0 ;
    }//点在线段上的判断

    bool parallel(Line v){
        return sgn((e-s)^(v.e-v.s))==0;
    }//两向量(对应的直线)平行

    int seg_cross_seg(Line v){
        int d1=sgn((e-s)^(v.s-s));
        int d2=sgn((e-s)^(v.e-s));
        int d3=sgn((v.e-v.s)^(s-v.s));
        int d4=sgn((v.e-v.s)^(e-v.s));
        if((d1^d2)==-2 && (d3^d4)==-2) return 2; //规范相交
        return  (d1==0 && sgn((v.s-s)*(v.s-e))<=0)||
                (d2==0 && sgn((v.e-s)*(v.e-e))<=0)||
                (d3==0 && sgn((s-v.s)*(s-v.e))<=0)||
                (d4==0 && sgn((e-v.s)*(e-v.e))<=0); //返回 1 非规范相交 0 不相交
    }

    int line_cross_seg(Line v){
        int d1 = sgn((e-s)^(v.s-s));
        int d2 = sgn((e-s)^(v.e-s));
        if((d1^d2)==-2) return 2;//规范相交
        return (d1==0||d2==0);//返回 1 非规范相交 0 不想交
    }//直线和线段相交判断

    int line_cross_line(Line v){
        if((*this).parallel(v))
            return v.relation(s)==3;//返回 1重合 0 平行
        return 2;//相交
    }//判断直线与直线之间的关系

    Point cross_point(Line v){
        double a1 = (v.e-v.s)^(s-v.s);
        double a2 = (v.e-v.s)^(e-v.s);
        return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
    }//求两直线的交点 前提：要保证直线不平行或重合

    double dis_point_to_line(Point p){
        return fabs((p-s)^(e-s))/length();
    }//点到直线的距离

    double dis_point_to_seg(Point p){
        if(sgn((p-s)*(e-s))<0 || sgn((p-e)*(s-e))<0)
            return min(p.distance(s),p.distance(e));
        return dis_point_to_line(p);
    }//点到线段的距离

    double dis_seg_to_seg(Line v){
        return min(min(dis_point_to_seg(v.s),dis_point_to_seg(v.e)),min(v.dis_point_to_seg(s),v.dis_point_to_seg(e)));
    }//线段到线段的距离 前提:两线段不相交 相交距离=0

    Point line_prog(Point p){
        return s + ( ((e-s)*((e-s)*(p-s)))/((e-s).len2()) );
    }//点p在直线上的投影

    Point symmetry_point(Point p){
        Point q = line_prog(p);
        return Point(2*q.x-p.x,2*q.y-p.y);
    }//点p关于直线的对称点
};

typedef Line line;
typedef Line segment;
typedef Line seg;
/*------------------------------------------------------------------ 圆 ------------------------------------------------------------------ */
struct circle{
    Point p;//圆心
    double r;//半径
    circle(){}circle(Point _p,double _r){p = _p;r = _r;}
    circle(double x,double y,double _r){p = Point(x,y);r = _r;}

    circle(Point a,Point b,Point c){
        Line u = Line((a+b)/2,((a+b)/2)+((b-a).rotLeft()));
        Line v = Line((b+c)/2,((b+c)/2)+((c-b).rotLeft()));
        p = u.cross_point(v);r = p.distance(a);
    }//三角形的外接圆

    circle(Point a,Point b,Point c,bool non){ //这里的参数 non 没有作用 只是为了和上面的外接圆函数区别
        Line u,v;
        double m = atan2(b.y-a.y,b.x-a.x), n = atan2(c.y-a.y,c.x-a.x);
        u.s = a;
        u.e = u.s + Point(cos((n+m)/2),sin((n+m)/2));
        v.s = b;
        m = atan2(a.y-b.y,a.x-b.x) , n = atan2(c.y-b.y,c.x-b.x);
        v.e = v.s + Point(cos((n+m)/2),sin((n+m)/2));
        p = u.cross_point(v);r = Line(a,b).dis_point_to_seg(p);
    }//三角形的内切圆

    void input(){p.input();scanf("%lf",&r);}//输入
    void output(){printf("%.2lf %.2lf %.2lf\n",p.x,p.y,r);}//输出

    bool operator == (circle v){return (p==v.p) && sgn(r-v.r)==0;}
    bool operator < (circle v)const{return ((p<v.p)||((p==v.p)&&sgn(r-v.r)<0));}

    double area(){return pi*r*r;}
    //圆的面积
    double circumference(){return 2*pi*r;}
    //圆的周长

    int relation(Point b){
        double dst = b.distance(p);
        if(sgn(dst-r) < 0)
            return 2;//在圆内
        else if(sgn(dst-r)==0)
            return 1;//在圆上
        return 0;//在圆外
    }//点与圆的关系

    int relation_seg(Line v){
        double dst = v.dis_point_to_seg(p);
        if(sgn(dst-r) < 0)
            return 2;//相交
        else if(sgn(dst-r) == 0)
            return 1;//相切
        return 0;//相离
    }//线段和圆的关系 比较的是圆心到线段距离的

    int relation_line(Line v){
        double dst = v.dis_point_to_line(p);
        if(sgn(dst-r) < 0)return 2;//相交
        else if(sgn(dst-r) == 0)return 1;//相切
        return 0;//相离
    }//直线和圆的关系

    int relation_circle(circle v){
        double d = p.distance(v.p);
        if(sgn(d-r-v.r) > 0)return 5;//相离
        if(sgn(d-r-v.r) == 0)return 4;//外切
        double l = fabs(r-v.r);
        if(sgn(d-r-v.r)<0 && sgn(d-l)>0)return 3;//相交
        if(sgn(d-l)==0)return 2;//内切
        if(sgn(d-l)<0)return 1;//内含
    }//圆与圆的关系

    int point_cross_circle(circle v,Point &p1,Point &p2){
        int rel = relation_circle(v);
        if(rel == 1 || rel == 5)return 0;//两个圆之间没有交点
        double d = p.distance(v.p);
        double l = (d*d+r*r-v.r*v.r)/(2*d);
        double h = sqrt(r*r-l*l);
        Point tmp = p + (v.p-p).trunc(l);
        p1 = tmp + ((v.p-p).rotLeft().trunc(h));
        p2 = tmp + ((v.p-p).rotRight().trunc(h));
        if(rel == 2 || rel == 4)return 1;//有1个交点
        return 2;//有两个交点
    }//求两个圆的交点


    int point_cross_line(Line v,Point &p1,Point &p2){
        if(!(*this).relation_line(v))return 0;
        Point a = v.line_prog(p);
        double d = v.dis_point_to_line(p);
        d = sqrt(r*r-d*d);
        if(sgn(d) == 0){
            p1 = a;
            p2 = a;
            return 1;
        }
        p2 = a + (v.e-v.s).trunc(d);
        p1 = a - (v.e-v.s).trunc(d);
        return 2;
    }//直线和圆的交点 返回交点的个数

    int get2_circle(Point a,Point b,double r1,circle &c1,circle &c2){
        circle x(a,r1),y(b,r1);
        int t = x.point_cross_circle(y,c1.p,c2.p);
        if(!t)return 0;
        c1.r = c2.r = r;
        return t;
    }//得到两个过a,b两点且半径为r1的圆

    int get_circle(Line u,Point q,double r1,circle &c1,circle &c2){
        double dis = u.dis_point_to_line(q);
        if(sgn(dis-r1*2)>0)return 0;
        if(sgn(dis) == 0){
            c1.p = q + ((u.e-u.s).rotLeft().trunc(r1));
            c2.p = q + ((u.e-u.s).rotRight().trunc(r1));
            c1.r = c2.r = r1;return 2;
        }
        Line u1 = Line((u.s + (u.e-u.s).rotLeft().trunc(r1)),(u.e + (u.e-u.s).rotLeft().trunc(r1)));
        Line u2 = Line((u.s + (u.e-u.s).rotRight().trunc(r1)),(u.e + (u.e-u.s).rotRight().trunc(r1)));
        circle cc = circle(q,r1);
        Point p1,p2;
        if(!cc.point_cross_line(u1,p1,p2))
            cc.point_cross_line(u2,p1,p2);
        c1 = circle(p1,r1);
        if(p1 == p2){
            c2 = c1;return 1;
        }
        c2 = circle(p2,r1);
        return 2;
    }//得到与直线u相切 且过点q 半径为r1的圆

    int get_circle(Line u,Line v,double r1,circle &c1,circle &c2,circle &c3,circle &c4){
        if(u.parallel(v))return 0;//两直线平行
        Line u1 = Line(u.s + (u.e-u.s).rotLeft().trunc(r1),u.e + (u.e-u.s).rotLeft().trunc(r1));
        Line u2 = Line(u.s + (u.e-u.s).rotRight().trunc(r1),u.e + (u.e-u.s).rotRight().trunc(r1));
        Line v1 = Line(v.s + (v.e-v.s).rotLeft().trunc(r1),v.e + (v.e-v.s).rotLeft().trunc(r1));
        Line v2 = Line(v.s + (v.e-v.s).rotRight().trunc(r1),v.e + (v.e-v.s).rotRight().trunc(r1));
        c1.r = c2.r = c3.r = c4.r = r1;
        c1.p = u1.cross_point(v1);
        c2.p = u1.cross_point(v2);
        c3.p = u2.cross_point(v1);
        c4.p = u2.cross_point(v2);
        return 4;
    }//求同时与直线u、v相切 且半径为r1的直线  返回生成的圆的个数

    int get_circle(circle cx,circle cy,double r1,circle &c1,circle &c2){
        circle x(cx.p,r1+cx.r),y(cy.p,r1+cy.r);
        int t = x.point_cross_circle(y,c1.p,c2.p);
        if(!t)return 0;
        c1.r = c2.r = r1;
        return t;
    }//同时与不相交圆cx cy相切 且半径为r1的圆 最多两个

    int tangent_line(Point q,Line &u,Line &v){
        int x = relation(q);
        if(x == 2)return 0;
        if(x == 1){
            u = Line(q,q + (q-p).rotLeft());
            v = u;
            return 1;
        }
        double d = p.distance(q);
        double l = r*r/d;
        double h = sqrt(r*r-l*l);
        u = Line(q,p + ((q-p).trunc(l) + (q-p).rotLeft().trunc(h)));
        v = Line(q,p + ((q-p).trunc(l) + (q-p).rotRight().trunc(h)));
        return 2;
    }//过一点作圆的切线 可能有两条


    double area_circle(circle v){
        int rel = relation_circle(v);
        if(rel >= 4)return 0.0;
        if(rel <= 2)return min(area(),v.area());
        double d = p.distance(v.p);
        double hf = (r+v.r+d)/2.0;
        double ss = 2*sqrt(hf*(hf-r)*(hf-v.r)*(hf-d));
        double a1 = acos((r*r+d*d-v.r*v.r)/(2.0*r*d));
        a1 = a1*r*r;double a2 = acos((v.r*v.r+d*d-r*r)/(2.0*v.r*d));
        a2 = a2*v.r*v.r;
        return a1+a2-ss;
    }//求两圆相交的面积

    double area_triangle(Point a,Point b){
        if(sgn((p-a)^(p-b)) == 0)return 0.0;
        Point q[5];
        int len = 0;
        q[len++] = a;
        Line l(a,b);
        Point p1,p2;
        if(point_cross_line(l,q[1],q[2])==2){
            if(sgn((a-q[1])*(b-q[1]))<0)
                q[len++] = q[1];
            if(sgn((a-q[2])*(b-q[2]))<0)
                q[len++] = q[2];
        }
        q[len++] = b;
        if(len == 4 && sgn((q[0]-q[1])*(q[2]-q[1]))>0)
            swap(q[1],q[2]);
        double res = 0;
        for(int i = 0;i < len-1;i++){
            if(relation(q[i])==0||relation(q[i+1])==0){
                double arg = p.rad(q[i],q[i+1]);
                res += r*r*arg/2.0;
            }else{
                res += fabs((q[i]-p)^(q[i+1]-p))/2.0;
            }
        }
        return res;
    }//求圆和三角形pab相交的面积
};

三维

/*------------------------ 三维几何 ------------------------------------------------------------------ */
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;

int sgn(double x){
    if(fabs(x) < eps)return 0;
    if(x < 0)return -1;
    else return 1;
}

/*--------------------- 点 ------------------------------------------------------------------ */

struct Point3{
    double x,y,z;
    Point3(double _x = 0,double _y = 0,double _z = 0){x = _x;y = _y;z = _z;}
    void input(){scanf("%lf%lf%lf",&x,&y,&z);}//输入
    void output(){printf("%.2lf %.2lf %.2lf\n",x,y,z);}//输出

    Point3 operator +(const Point3 &b)const{return Point3(x+b.x,y+b.y,z+b.z);}
    Point3 operator -(const Point3 &b)const{return Point3(x-b.x,y-b.y,z-b.z);}
    Point3 operator *(const double &k)const{return Point3(x*k,y*k,z*k);}
    Point3 operator /(const double &k)const{return Point3(x/k,y/k,z/k);}
    bool operator ==(const Point3 &b)const{return sgn(x-b.x) == 0 && sgn(y-b.y) == 0 && sgn(z-b.z) == 0;}
    bool operator <(const Point3 &b)const{return sgn(x-b.x)==0?(sgn(y-b.y)==0?sgn(z-b.z)<0:y<b.y):x<b.x;}

    double len(){return sqrt(x*x+y*y+z*z);}
    double len2(){return x*x+y*y+z*z;}
    double distance(const Point3 &b)const{return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y)+(z-b.z)*(z-b.z));}

    double operator *(const Point3 &b)const{return x*b.x+y*b.y+z*b.z;}//点乘
    Point3 operator ^(const Point3 &b)const {return Point3(y * b.z - z * b.y, z * b.x - x * b.z, x * b.y - y * b.x);}//叉乘

    double rad(Point3 a,Point3 b){
        Point3 p = (*this);
        return acos( ( (a-p)*(b-p) )/ (a.distance(p)*b.distance(p)) );
    }//求pa pb之间的角度

    Point3 trunc(double r){
        double l = len();
        if(!sgn(l))return *this;
        r /= l;
        return Point3(x*r,y*r,z*r);
    }//变换长度
};
typedef Point3 Vector3;

/*------------------------- 直线 ------------------------------------------------------------------ */

struct Line3{
    Point3 s,e;
    Line3(){}
    Line3(Point3 _s,Point3 _e){s = _s;e = _e;}
    bool operator ==(const Line3 v){return (s==v.s)&&(e==v.e);}
    void input(){s.input();e.input();}//输入
    double length(){return s.distance(e);} 

    double dis_point_to_line(Point3 p){return ((e-s)^(p-s)).len()/s.distance(e);}
    //点到直线距离

    double dis_point_to_seg(Point3 p){
        if(sgn((p-s)*(e-s)) < 0 || sgn((p-e)*(s-e)) < 0)
        return min(p.distance(s),e.distance(p));
    }//点到线段距离


    Point3 line_prog(Point3 p){
        return s + ( ((e-s)*((e-s)*(p-s)))/((e-s).len2()) );
    }//返回点p在直线上的投影

    Point3 rotate(Point3 p,double ang){
        if(sgn(((s-p)^(e-p)).len()) == 0)return p;
        Point3 f1 = (e-s)^(p-s);
        Point3 f2 = (e-s)^(f1);
        double len = ((s-p)^(e-p)).len()/s.distance(e);
        f1 = f1.trunc(len); f2 = f2.trunc(len);
        Point3 h = p+f2;
        Point3 pp = h+f1;
        return h + ((p-h)*cos(ang)) + ((pp-h)*sin(ang));
    }//p绕此向量逆时针arg角度

    bool point_on_seg(Point3 p){return sgn( ((s-p)^(e-p)).len() ) == 0 && sgn((s-p)*(e-p)) == 0;}
    //判断点是否在直线上
};


/*----------------------------- 平面 ------------------------------------------------------------------ */


struct Plane{
    Point3 a,b,c,o;//`平面上的三个点，以及法向量`
    Plane(){}
    Plane(Point3 _a,Point3 _b,Point3 _c){a = _a;b = _b;c = _c;o = pvec();}
    Point3 pvec(){return (b-a)^(c-a);}

    Plane(double _a,double _b,double _c,double _d){
        o = Point3(_a,_b,_c);
        if(sgn(_a) != 0)
        a = Point3((-_d-_c-_b)/_a,1,1);
        else if(sgn(_b) != 0)
        a = Point3(1,(-_d-_c-_a)/_b,1);
        else if(sgn(_c) != 0)
        a = Point3(1,1,(-_d-_a-_b)/_c);
    }//求平面ax+by+cz+d = 0

    bool point_on_plane(Point3 p){return sgn((p-a)*o) == 0;}
    //判断点是否在平面上

    double angle_plane(Plane f){return acos(o*f.o)/(o.len()*f.o.len());}
    //求两平面夹角

    int cross_line(Line3 u,Point3 &p){
        double x = o*(u.e-a);
        double y = o*(u.s-a);
        double d = x-y;
        if(sgn(d) == 0)return 0;
        p = ((u.s*x)-(u.e*y))/d;
        return 1;
    }//`平面和直线的交点，返回值是交点个数`

    Point3 point_to_plane(Point3 p)
    {
        Line3 u = Line3(p,p+o);
        cross_line(u,p);
        return p;
    }//求点到平面最近点(也就是投影)

    int cross_plane(Plane f,Line3 &u){
        Point3 oo = o^f.o;
        Point3 v = o^oo;
        double d = fabs(f.o*v);
        if(sgn(d) == 0)return 0;
        Point3 q = a + (v*(f.o*(f.a-a))/d);
        u = Line3(q,q+oo);
        return 1;
    } //求平面和平面的交线

 };

原先的几何板子

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef __int64 LL;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int INF=0x3f3f3f3f;
const ll inf=0x3f3f3f3f3f3f3f3f;//inf=(1ll<<60)
const int mod=1e9+7;
const int base =131;
const int N=1e6+10;

const double eps=1e-8;
const double pi=acos(-1.0);

int dcmp(double x,double y)
{
    if(fabs(x-y)<eps) return 0;
    else return x<y?-1:1;
}
//判断x是否等于y


int sgn(double x)
{
    if(fabs(x)<eps) return 0;
    else return x<0?-1:1;
}
//判断x是否等于0


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;}
//向量点积
//dot(a,b)>0 说明 a,b夹角为锐角
//dot(a,b)<0 钝角
//dot(a,b)=0 直角

double Len(Vector A){return sqrt(Dot(A,A));}
//求向量A的长度


double Dist(Point A,Point B)
{
    return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
}

double Distance(Point A,Point B)
{
    return hypot(A.x-B.x,A.y-B.y);
}
//计算两点之间的距离 hypot计算三角形的斜边长


double Len2(Vector A)
{ 
    return Dot(A,A);
}
//求向量A的长度的平方


double Cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
//AXB的叉积 注意 叉积有顺序的
//AXB>0 B在A的逆时针方向
//AXB<0 B在A的顺时针方向
//AXB=0 B与A共线，可能是同方向的 也可能是反方向的


double Area2(Point A,Point B,Point C)
{
    return fabs(Cross(B-A,C-A));
}
//计算a,b,c三个点形成的平行四边形的面积


Vector Rotate(Vector A,double rad)
{
    return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}
//将A向量逆时针旋转rad度 当rad=90°时 rad=pi/2


Vector Normal(Vector A)
{
    return Vector(-A.y/Len(A),A.x/Len(A));
}
//求单位法向量


bool Parallel(Vector A,Vector B)
{
    return Cross(A,B)==0;
}
//判断向量是否平行


Vector trunc(Vector A, double len){ // len=1时 求的就是单位向量
    double l=hypot(A.x,A.y);
    if(!sgn(l)) return A;
    len/=l;
    return Point(A.x*len,A.y*len);
}//求模长为len的向量

/*--------------------------- 直线 ------------------------------------------------------------------ */
struct Line
{
    Point p1,p2;
    Line(){}
    Line(Point p1,Point p2):p1(p1),p2(p2){}

    Line(Point p,double angle){ //0<=angle<pi
        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 / b);
            p2 = Point(1, (-c - a) / b);
        }
        //求出直线ax+by+c=0;
    }
};


/*--------------------------------- 线段------------------------------------------------------------------ */
typedef Line Segment;
int Point_Line_relation(Point p,Line v)
{
    int c=sgn(Cross(p-v.p1,v.p2-v.p1));
    if(c<0) return 1;//点在直线的左边
    if(c>0) return 2;//点在直线的右边
    return 0;//点在直线上
}//判断点与直线的位置关系

bool Point_on_seg(Point p,Segment v)
{
    return sgn(Cross(p-v.p1,v.p2-v.p1))==0&& sgn(Dot(p-v.p1,p-v.p2))<=0;
}
//判断点与线段的关系
//0 点不在线段上
//1 点在直线上


double Dis_point_line(Point p,Line v)
{
    return fabs(Cross(p-v.p1,v.p2-v.p1))/Distance(v.p1,v.p2);
}//求点到直线的距离


Point Point_line_proj(Point p,Line v)
{
    double kk=Dot(v.p2-v.p1,p-v.p1)/Len2(v.p2-v.p1);
    return v.p1+(v.p2-v.p1)*kk;
}//求点在直线上的投影

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_poinst_seg(Point p,Segment v)
{
    if(sgn(Dot(p-v.p1,v.p2-v.p1))<0 || sgn(Dot(p-v.p1,v.p1-v.p2))<0)
        return min(Distance(p,v.p1),Distance(p,v.p2));//Distance 计算两点之间的距离
    return Dis_point_line(p,v);//点的投影在线段上
}
//求点到线段的距离

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;//平行
    }
    else return 2;//相交
}//判断两条直线的关系


Point Cross_point(Point a,Point b,Point c,Point d)//Line ab ,Line cd
{
    double s1=Cross(b-a,c-a);
    double s2=Cross(b-a,d-a);
    //前提！保证s2-s1!=0 即ab cd不共线且不平行
    return Point(c.x*s2-d.x*s1,c.y*s2-d.y*s1)/(s2-s1);
}//求两条直线的交点

bool Cross_segment(Point a,Point b,Point c,Point d)//Line ab ,Line cd
{
    double c1=Cross(b-a,c-a),c2=Cross(b-a,d-a);
    double d1=Cross(d-c,a-c),d2=Cross(d-c,b-c);
    return sgn(c1)*sgn(c2)<0 && sgn(d1)*sgn(d2)<0;
    //1-相交     0-不相交
}//判断两个线段是否相交


Point Cross_segment_point(Segment v1,Segment v2)
{

}//求两个线段的交点




/*------------------------------------------------------------------ 圆------------------------------------------------------------------ */
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=Distance(p,C.c);
    if(sgn(dst-C.r)<0)return 0;//点在圆内
    if(sgn(dst-C.r)==0)return 1;//点在圆上
    return 2;//点在圆外
}//判断点与圆的关系

int Line_circle_relation(Line v,Circle C)
{
    double dst=Dis_point_line(C.c,v);
    if(sgn(dst-C.r)<0)return 0;//直线与圆相交
    if(sgn(dst-C.r)==0)return 1;//直线与圆相切
    return 2;//直线在圆外
}//判断直线与圆的位置关系

int Seg_circle_relation(Segment v,Circle C)
{
    double dst=Dis_point_line(C.c,v);
    if(sgn(dst-C.r)<0)return 0;//线段与圆相交
    if(sgn(dst-C.r)==0)return 1;//线段与圆相切
    return 2;//线段在圆外
}//判断线段与圆的位置关系


int Line_cross_circle(Line v,Circle C,Point &point_a,Point& point_b)
{
    if(Line_circle_relation(v,C)==2)return 0;//无交点
    Point q=Point_line_proj(C.c,v);//求圆心在直线上的投影点
    double dst=Dis_point_line(C.c,v);//圆心到直线的距离
    double kk=sqrt(C.r*C.r-dst*dst);
    if(sgn(kk)==0)
    {
        point_a=q;
        point_b=q;
        return 1;//一个交点 直线与圆相切
    }
    Point nn=(v.p2-v.p1)/Len(v.p2-v.p1);//单位向量
    point_a=q+nn*kk;
    point_b=q-nn*kk;
    return 2;//两个交点
}//求直线与圆的交点 pa,pb是交点 返回交点的个数



/*------------------------------------------------------------------ 三维空间点和向量------------------------------------------------------------------ */

struct Point3
{
    double x,y,z;
    Point3(){}
    Point3(double x,double y,double z):x(x),y(y),z(z){}
    //向量的运算操作
    Point3 operator +(Point3 B){return Point3(x+B.x,y+B.y,z+B.z);}
    Point3 operator -(Point3 B){return Point3(x-B.x,y-B.y,z-B.z);}
    Point3 operator *(double k){return Point3(x*k,y*k,z*k);}
    Point3 operator /(double k){return Point3(x/k,y/k,z/k);}
    bool operator ==(Point3 B){return sgn(x-B.x)==0 && sgn(y-B.y)==0 && sgn(z-B.z)==0;}

};//三维 点和向量
typedef Point3 Vector3;

double Distance(Point3 A,Point3 B)
{
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)+(A.z-B.z)*(A.z-B.z));
}//求两点之间的距离



double Dot(Vector3 A,Vector3 B)
{
    return A.x*B.x+A.y*B.y+A.z*B.z;
}
//A·B的点积
//dot(a,b)>0 说明 a,b夹角为锐角
//dot(a,b)<0 钝角
//dot(a,b)=0 直角

double Len(Vector3 A)
{
    return sqrt(Dot(A,A));
}
//求向量A的长度

double Len2(Vector3 A)
{
    return Dot(A,A);
}
//求向量A的长度的平方

double Angle(Vector3 A,Vector3 B)
{
    return acos(Dot(A,B)/Len(A)/Len(B));
}
//求向量A B的夹角

Vector3 Cross(Vector3 A,Vector3 B)
{
    return Point3(A.y*B.z-A.z*B.y,A.z*B.x-A.x*B.z,A.x*B.y-A.y*B.x);
}
//三维叉积

double Area2(Point3 A,Point3 B,Point3 C)
{
    return Len(Cross(B-A,C-A));
}
//求三点形成的平行四边形=三角形的面积*2



/*------------------------------------------------------------------空间直线------------------------------------------------------------------ */


struct Line3
{
    Point3 p1,p2;
    Line3(){}
    Line3(Point3 p1,Point3 p2):p1(p1),p2(p2){}
};
typedef Line3 Segment3;



/*------------------------------------------------------------------ 平面 ------------------------------------------------------------------ */
struct Plane
{
    Point3 p1,p2,p3;
    Plane(){}
    Plane(Point3 p1,Point3 p2,Point3 p3):p1(p1),p2(p2),p3(p3){}
};//平面


/*--------------------------------------------复数 ---------------------------------------*/
struct Complex{
    double a,b;

    Complex(){}
    Complex(double a,double b):a(a),b(b){}
    Complex operator + (Complex t){return Complex(a+t.a,b+t.b);}
    Complex operator - (Complex t){return Complex(a-t.a,b-t.b);}
    Complex operator * (Complex t){// (ac-bd)+(ad+bc)i
        double c=t.a,d=t.b;
        return Complex(a*c-b*d,b*c+a*d);
    }
    Complex operator / (Complex t){// (ac+bd)/(c^2+d^2) + (bc-ad)/(c^2+d^2)i
        double c=t.a,d=t.b;
        return Complex((a*c+b*d)/(c*c+d*d),(b*c-a*d)/(c*c+d*d));
    }

};

double Mo(Complex t){ //求模长
    return sqrt(t.a*t.a+t.b*t.b);
}