寄算几何基础

$\text{时}\text{无}\text{英}\text{雄}，\text{使}\text{竖}\text{子}\text{成}\text{名}$$时无英雄，使竖子成名$

数

取得数的符号，比较两数的大小

const double EPS = (1e-9) ;
int sign (double x) {return x < -EPS ? -1 : x > EPS ;} 
int cmp (double a , double b) {return sign (a - b) ;}

点

点及加减乘除运算

$alpha()$$alpha()$：幅角计算

$read()/write()$$read()/write()$：输入输出

$rot90()$$rot90()$：旋转90度

$unit()$$unit()$：单位向量

​x

class Point {

    public :
        double x , y ;
        Point (double x = 0, double y = 0) {
            this->x = x ;
            this->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 ) ;
        }

        double alpha () {
            return atan2 (y , x);
        }
        void read () {
            scanf ("%lf%lf" , &x , &y) ;
        }
        void write () {
            printf ("(%f,%f)\n" , x , y) ;
        }
        Point rot90 () {
            return Point (-y , x) ;
        }

        double abs2 () {
            return x * x + y * y
                   ;
        }
        double abs () {
            return sqrt (abs2 ()) ;
        }


};


Point operator * (double k , Point p) {
    return Point (k * p.x , k * p.y) ;
}
Point operator / (Point p , double k) {
    return Point (p.x / k , p.y / k) ;
}
Point unit (Point p) {
    return (p / p.abs () );
}
int operator == (Point p1 , Point p2)  {
    return cmp(p1.x , p2.x) == 0 && cmp (p1.y , p2.y ) == 0 ;
}

double getdis (Point p1 , Point p2) {
    return sqrt ((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) *  (p1.y - p2.y) );
}

向量与线

向量运算：点积和叉积

点积的物理意义是做功。

叉积的意义是面积和绕向，也可以判断向量是否平行。

xxxxxxxxxx
double dot (Point p1 , Point p2) {
    return p1.x * p2.x + p1.y * p2.y ;
}
double det (Point p1 , Point p2) {
    return p1.x * p2.y - p1.y * p2.x ;
}

极角排序

C++的atan2()函数速度慢，精度低。

先将平面分为上下两半，上面的比下面小。

在同一面的，用叉积来判断。

判断直线是否平行，求直线的交点

xxxxxxxxxx
bool chechLL (Point p1 , Point p2 , Point q1 , Point q2) {
    double a1 = cross (q1 , q2 , p1 ) , a2 = -cross (q1 , q2 , p2) ;
    return sign (a1 + a2) != 0 ;
}
Point isLL (Point p1 , Point p2 , Point q1 , Point p2) {
    double a1 = cross (q1 , q2 , p1 ) , a2 = -cross (q1 , q2 , p2) ;
    return (a2 * p1  + a1 * p2) / (a1 + a2) ;
}

判断线段是否相交，求线段交点

xxxxxxxxxx
bool intersect (double l1 , double r1 , double l2 , double r2) {
    if (l1 > r1) swap (l1 , r1) ;
    if (l2 > r2) swap (l2 , r2) ;
    
    return !(cmp (r1 , l2) == -1 || cmp (r2 , l1) == -1) ;
}
bool isSS (Point p1 , Point p2 , Point q1 , Point q2) {
    return intersect (p1.x , p2.x , q1.x , q2.x) &&
            intersect (p1.y , q2.y , q1.y , q2.y) &&
            crossOp (p1 , p2 , q1) * crossOp (p1 , p2 , q2) <= 0 &&
            crossOp (q1 , q2 , p1) * crossOp (q1 , q2 , p2) <= 0 ;
}

例题

• 给出$n$$n$个点的简单多边形，求能放进去的最长线段。$n\le 200$$n≤200$
• 枚举顶点作为端点即可。

回到上一级