计算几何学习笔记

· · 个人记录

常用技巧

点积

\vec{a} \cdot \vec{b} = |a| |b| cos \theta = x_{a} * x_{b} + y_{a} * y_{b}

可以用来判断两个向量是否垂直

叉积

\vec{a} \times \vec{b} = |a| |b| sin \theta = x_{a} * y_{b} - y_{a} * x_{b} ------------ ## 多边形面积 将点逆时针排序后做一圈叉积，所得和的 $1/2$ 即为多边形面积 ------------ ## 旋转 $(x,y)$ 以原点为中心旋转 $\theta$ 度 设 $$ \vec{a} = ( x ,y ) = ( t cos\alpha , t sin\alpha ) $$ 旋转后 $$ \vec{a'} = ( t cos( \alpha + \theta ) , t sin( \alpha + \theta ) ) $$ $$ = ( t( cos\alpha cos \theta - sin\alpha sin \theta ) , t ( sin\alpha cos \theta + sin\theta cos\alpha ) ) $$ $$ = ( cos\theta x - sin\theta y , cos\theta y + sin\theta x ) $$ ------------ ## 判断点是否在直线上 点 $P$ 在直线 $AB$ 上当且仅当 $ \vec{AP} \times \vec{BP} =0

判断点是否在线段上

点 P 在线段 AB 上当且仅当 |PA| + |PB| = |AB|

计算点到直线的距离

随意取两点叉积求出面积，用三角形面积公式求得距离

计算点到线段的距离

求出高后，特判一下点和两个端点的连线是否在高的同一侧，如果是说明高不在三角形内，结果在两条连线中取 min

求两直线的交点

假设求直线 AB 和直线 CD 的交点。

求出三角形 ABC 和 ABD 的面积，得到 OC 和 OD 的比值。

根据是否在同一侧判断即可

直线与圆的交点

旋转使直线斜率为 0

用纵坐标差求出圆心到直线作垂线的交点的坐标，然后勾股定理求出弦长，得出交点坐标再转回去

圆与圆的交点

旋转使两圆圆心纵坐标相等

求出三角形面积后求出高，勾股定理求出坐标后旋转回去

求凸壳

把所有点以 x 为第一关键字， y 为第二关键字排序，然后正反跑两遍分别求出上下凸壳

代码（P2742）：

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

typedef struct vec{
    double x,y;
    vec() {}
    vec(double _x,double _y):x(_x),y(_y) {}
    vec operator - (vec a) {return vec(x-a.x,y-a.y);}
    vec operator + (vec a) {return vec(x+a.x,y+a.y);}
    double operator * (vec a) {return x*a.y-y*a.x;}
}vec;

const double eps=1e-8;
vec p[10010];
double ans;
int n,s[10010],siz,downtag;

bool cmp(vec a,vec b) {return (fabs(a.x-b.x)<eps)?a.y<b.y:a.x<b.x;}

double dis(vec a,vec b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
    sort(p+1,p+1+n,cmp);
    s[++siz]=1; s[++siz]=2;
    for(int i=3;i<=n;i++){
        while(siz>=2 && (p[s[siz]]-p[s[siz-1]])*(p[i]-p[s[siz]])<0) siz--;
        s[++siz]=i;
    }
    downtag=siz; s[++siz]=n-1;
    for(int i=n-2;i>=1;i--){
        while(siz-downtag>=1 && (p[s[siz]]-p[s[siz-1]])*(p[i]-p[s[siz]])<0) siz--;
        s[++siz]=i;
    }
    for(int i=1;i<siz;i++) ans+=dis(p[s[i]],p[s[i+1]]);
    printf("%.2f",ans);
    return 0;
}