「OI之路」07其他-6计算几何

计算几何
more1
more2

辅助函数

1
double atan2(double y,double x)

向量相关

主要见线性代数一章

向量旋转:这个很好推,考虑两个基向量即可,$(a,b)逆时针旋转 \theta ->(acos\theta -bsin\theta ,asin\theta +bcos\theta )$

三角形的五心

外心:垂直平分线交点

重心:中线交点,重心到顶点=2*重心到对边中点,平分面积,到三个顶点距离的平方和最小,坐标为平均数,到三个顶点的向量和=零向量

垂心:垂线交点,三角形垂心到任一顶点=2*其外心到对边,单位圆上为三点坐标之和

内心:角平分线交点,直角三角形内心的$r=\frac{a+b-c}{2}$,圆内三点的三角形内心=那三段圆弧的中点形成三角形的垂心

欧拉线:外心O,重心G,垂心H,三点共线,2OG=GH

几何图形

求多边形(可以凹)的面积
相邻两点(逆时针的话,可以不用绝对值,所以能模了,尽管面积可能是负数,最后总是正数)到坐标原点的叉积和
例题:HDU-2036

随机任意多边形的数据
[Wf2017]Airport Construction

直线交点
建议画图,一条直线与另外两点的叉积面积比=高的比=另一条直线被交点所分的两部分之比

1
2
3
4
5
6
7
Pt check(Pt a,Pt b,Pt c,Pt d)//尚未验证正确性
{
Pt t1=b-a,t2=d-c,t3=c-a;
ll A=cross(t1,t2),B=cross(t3,t2);
double xx=a.x+(double)B/A*t1.x,yy=a.y+(double)B/A*t1.y;
return (Pt){xx,yy};
}

过圆外一点的切线:求点与圆心的直线然后用asin旋转

板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#define double long double
const double PI=acos(-1);
const double eps=1e-7;
struct V
{
double x,y;V(double _x=0,double _y=0){x=_x,y=_y;}
double ss(){return sqrt(x*x+y*y);}
V operator + (V b){return V(x+b.x,y+b.y);}
V operator - (V b){return V(x-b.x,y-b.y);}
V operator * (double b){return V(x*b,y*b);}
double operator * (V b){return x*b.y-y*b.x;}
double cross(V a,V b){return V(a.x-x,a.y-y)*V(b.x-x,b.y-y);}
V rotate(double rad){return (V){x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad)};}
};
double sp(V a,V b)
{
if(fabs(a.x)<=eps and fabs(a.y)<=eps) puts("err");
if(fabs(b.x)<=eps and fabs(b.y)<=eps) puts("err");
double c=atan2(a.y,a.x),d=atan2(b.y,b.x);
return min(fabs(c-d),PI*2-fabs(c-d));
}
V chui_zu(V a,V b)
{
double dis=fabs(a*b)/(b-a).ss(),len=(b-a).ss();
return (a-b).rotate(PI/2)*(dis/len)*(a*b>0?1:-1);
}

基础题

雅礼冬令营集训2019 D7t3

PKUSC2018D2T3 PKUSC

转载

尚未学习

y>=kx+b(y<=kx+b同理)的半平面交的并集是一个上凸壳,我们可以把它对偶成凸包,即是将一条直线的 (k,b)视为一个点 (k,b),然后做一个下凸壳。这样我们就可以合并半平面交了,即为做这个对偶凸包的闵可夫斯基和(就是(a,b)和(c,d)合并起来后为(a+b,c+d)。因为ax+b+cx+d=>(a+c,b+d))。而闵可夫斯基和可以双指针在两个凸壳上面移动来解决,开始时候,两个指针p1,p2都在1位置,之后判断(p1,p2+1),(p1+1,p2)和(p1,p2)的斜率哪个更大(叉积判断即可),以此来移动指针,这样相当于直接扔掉了一列或者一行。

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/7158.html
转载请注明出处,谢谢!