typedef complex <double> Point;// 复数类来简化代码
Point a;
a.real(), a.imag();// a的实部与虚部 对应二维平面 x,y 
abs(a);// 向量a的模/a到原点距离 
norm(a);// 模的平方 
arg(a);// a对应的角度 （弧度制 
conj(a);// a的共轭 （来计算点积与叉积
polar(r, theta);// 返回极坐标 (r, theta) 的 Point型 

double Det(const Point & a, const Point & b){//叉积 
    return (conj(a) * b).imag();
}

double Dot(const Point & a, const Point & b){//点积 
    return (conj(a) * b).real();
}

int sgn(double x) {//浮点数的正负比较 
    if(abs(x) < eps) return 0;
    if(x < 0) return -1;
    return 1;
}

Point Rotate(const Point & o , double theta){//仿射变换 将一个点绕原点 逆时针旋转theta 
    return (Point) {o.real() * cos(theta) - o.imag() * sin (theta), o.real() * sin(theta) + o.imag() * cos(theta)};
}

Point ConvertPoint(const Point & u ,const Point & v, const Point & o){//坐标变换 
    // A * u + B * v = o 不成立的情况下 
    //求o在 u ,v 为基底的情况下的坐标 
    return (Point) {Det(o, v) / Det(u, v), Det(o, u) / Det(v, u)};
}

struct Line : public vector <Point>{//存储直线上的两点 或表示线段 
    Line(){};
    Line(const Point & a, const Point & b){
        push_back(a);
        push_back(b);
        return;
    }
};

Point Vec(const Point & a){//单位向量 
    return a / abs(a);
}

Point Vec(const Line & a) {//方向向量 
    return a[1] - a[0];
}

Point LineIntersection(const Line & a, const Line & b){//直线的交 
    Point u = a[0] - b[0];
    double k1 = Det(Vec(a), Vec(b));
    double k2 = Det(Vec(b), u);
    if(!sgn(k1))//当方向向量共线时 返回 a的端点 外面判断是否平行 
        return a[0];
    return a[0] + Vec(a) * k2 / k1;
}

bool SegmentIntersection(const Line & a, const Line & b){ //两条线段是否存在交点 
    if(max(a[0].real(), a[1].real()) < min(b[0].real(), b[1].real())) return 0; 
    if(max(b[0].real(), b[1].real()) < min(a[0].real(), a[1].real())) return 0;
    if(max(a[0].imag(), a[1].imag()) < min(b[0].imag(), b[1].imag())) return 0;
    if(max(b[0].imag(), b[1].imag()) < min(a[0].imag(), a[1].imag())) return 0;
    Point t1 = Vec(a), t2 = Vec(b);
    return (sgn(Det(a[0] - b[0], t2)) * sgn(Det(a[1] - b[0], t2)) <= 0) && (sgn(Det(b[0] - a[0], t1)) * sgn(Det(b[1] - a[0], t1)) <= 0); 
}

int LSFLAG = 0;//用于判断交点是否存在 是否在线段上 
Point LSIntersection(const Line & a, const Line & b){//线段与直线的交 a为线段 b为直线 
    Point c = LineIntersection (a, b);
    LSFLAG = 0;
    if(sgn(Det(a[0] - b[0], Vec(b))) * sgn(Det(a[1] - b[0], Vec(b))) > 0 ){
        LSFLAG = -1;
        return c;
    }
    if(!sgn(Det(Vec(a), Vec(b)))) LSFLAG = -1;//平行 或  重合 交点无意义 
    else{
        if(sgn(Dot(a[0] - c, a[1] - c)) <= 0) return c;//交点在线段上 
        else LSFLAG = -1;//交点不在线段上 
    }
    return c;
}

Point CrossVP(const Line & v, const Point & u){//找点到直线距离（最近点 返回垂足 
    if(!sgn(v[0].real() - v[1].real()) && !sgn(v[0].imag() - v[1].imag())) return v[0];
    if(sgn(Dot(Vec(v), u - v[0])) < 0) return v[0];//删掉两行是直线 一行不删是线段 
    if(sgn(Dot(Vec(v), u - v[1])) > 0) return v[1];//删掉这行是射线
    double a = Dot(Vec(v), u - v[0]);
    return v[0] + a / norm(Vec(v)) * Vec(v);
}