计算几何基础

一.精度

1.比较两数大小

int dcmp(double x,double y)
{
    if(fabs(x-y)<eps)return 0;
    if(x>y)return 1;
    return -1;
}

2.判断浮点数符号

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

eg.1 计算几何spj hacker

nan值跟任何数比较除了!=,都是false

二.点

1.表示

struct Point
{
    double x,y;
};

2.判断两点是否重合

bool is_same(Point a,Point b)
{
    return !dcmp(a.x,b.x)&&!dcmp(a.y,b.y);
}

三.向量

1.表示

同点的表示

2.基本运算

(1)+ - * ^

Point operator+(Point a,Point b){return {a.x+b.x,a.y+b.y};}
Point operator-(Point a,Point b){return {a.x-b.x,a.y-b.y};}
Point operator*(double t,Point a){return {t*a.x,t*a.y};}
double operator*(Point a,Point b){return a.x*b.x+a.y*b.y;}
double operator^(Point a,Point b){return a.x*b.y-a.y*b.x;}

(2)基本应用

向量长度:|v|=sqrt(vv);
向量夹角:cosθ=ab/|a|/|b|;
向量投影:|a|cosθ=ab/|b|;
向量垂直:ab=0;

3.向量逆时针旋转θ

Point rotate(Point a,double θ)
{
    return {a.x*cosθ-a.y*sinθ,a.x*sinθ+a.y*cosθ};
}

4.to_left测试//判断点是否在直线左侧

bool to_left(Point v,Point a,Point b)//v是否在ab左侧
{
    return (b-a)^(v-a)>0;
}

四.线段

1.点是否在线段上

先判断点是否在线段所在直线上(叉积),在判断点是否在线段上(点积)

bool on_line(Point v,Point a,Point b)
{
    if(sign((b-a)^(v-a))!=0)return false;
    return sign((v-a)*(v-b))<=0;
}

2.判断两线段是否相交

两次to_left测试

bool is_intersection(Point a,Point b,Point u,Point v)
{
    return sign(((b-a)^(u-a))*((b-a)^(v-a)))<=0&&sign(((v-u)^(a-u))*((v-u)^(b-u)))<=0;
}

五.直线

1.表示

struct Line{
    Point p,v;
};

2.求点到直线的距离

double point_to_line(Point a,Line b)
{
    Point p=b.p,v=b.v;
    return fabs(((a-p)^v)/sqrt(v*v));
}

3.求点到直线的投影

Point Projection(Point a,Line b)
{
    Point p=b.p,v=b.v;
    double t=(a-p)*v/(v*v);
    return p+t*v;
}

4.求两直线交点

求交点先判断是否相交

Point get_line_intersection(Point p,Point v,Point q,Point w)
{
    Point u=p-q;
    double t=(u^w)/(w^v);
    return p+t*v;
}
Point get_line_intersection(Line a,Line b)
{
    return get_line_intersection(a.p,a.v,b.p,b.v);
}

eg.

https://ac.nowcoder.com/acm/contest/27249/E Operation Love
虽然给了20个点,但是我们只需要三个点就可以判断手的左右
手上有三个点a,b,c组成了两条边ab,bc.且|ab|=9,|bc|=8.
我们只需要判断a在bc的左侧还是右侧即可

if(to_left(a,b,c))puts("right");
else puts("left");

eg.

https://ac.nowcoder.com/acm/contest/27249/C Mr.Main and Windmills
给我们一个起点一个终点,在起点终点的连线的一侧有N个点
我们知道世界上任何两个东西,我们站在不同的位置去观察,这两个东西的左右性可能互换
即有这种情况,我们有物品a,b,我们站在s点,a在b的左侧,我们站在t点,a在b的右侧.
那两个点左右性互换的分界点在哪呢,答案是在两个点的连线上
故此题就是求由N个点能够组成的N*N/2条直线与起点终点构成的线段的交点

for(int i=1;i<=cnt;i++)     //cnt是直线的数量
{
    Point p=get_line_intersection(line[i],l);
    if(!check_point(p))continue;
    int u=line[i].u,w=line[i].w;
    ans[u].push_back(p);
    ans[w].push_back(p);
}
for(int i=1;i<=n;i++)sort(ans[i].begin(),ans[i].end(),cmpp);

eg.

Magic Rabbit Magic Rabbit
题意是求目标点是否在给的三个点内部(包含边界)
注意三角形的退化(线段,点),要特判

六.多边形

一般按逆时针顺序、不一定满足凸性、注意第一个点与最后一个点

1.表示

struct Polygon{
    vector<Point>p;
};

2.多边形求面积

double get_area(Polygon pol)
{
    double res=0;
    int siz=pol.p.size();
    for(int i=0;i<siz;i++)
    {
        Point a=pol.p[i],b=pol.p[(i+1)%siz];
        res+=a^b;
    }
    return res;
}

3.判断点是否在多边形内

(1)光线投射(边界问题)
(2)回转数法(反三角函数，精度与效率问题)
(3)Sunday’s algorithm

int Sunday_alg(Point a,Polgon b)
{
    int res=0;
    Line l={a,{1,0}};
    int siz=b.size();
    for(int i=0;i<siz;i++)
    {
        Point p,q;
        p=b.p[i],q=b.p[(i+1)%siz];
        if(on_line(a,p,q))return 0x3f3f3f3f;
        bool flag=to_left(a,p,q);
        if(p.y>q.y)
        {
            if(a.x<p.x&&a.y==p.y)continue;
        }
        else
        {
            if(a.x<q.x&&a.y==q.y)continue;
        }
        if(flag)
        {
            if(to_left(q,a,{a+Point{1,0}})&&to_right(p,a,{a+Point{1,0}}))res++;
        }
        else
        {
            if(to_left(p,a,{a+Point{1,0}})&&to_right(q,a,{a+Point{1,0}}))res--;
        }
    }
    return res;
}

边界情况
点在多边形上:特判
交点为多边形顶点:将该顶点视作在射线上方
若多边形为凸多边形可以做n次to_left测试

七.圆

1.表示

struct Circle{
    Point c;
    double r;
};