网站和二级目录权重,单位装专用的网站网页归档,WordPress开发过程,网站开发部门工资入什么科目文章目录直线#xff1a;图形#xff1a;求垂足求两圆交点直线与圆交点多边形问题判断一个点是否在任意多边形内部Pick定理凸包求点集的凸包水平法#xff1a;增量法#xff1a;半平面半平面交求半平面交直线#xff1a;
struct Line{point p,v;Line(){}Line(point _p.po…
文章目录直线图形求垂足求两圆交点直线与圆交点多边形问题判断一个点是否在任意多边形内部Pick定理凸包求点集的凸包水平法增量法半平面半平面交求半平面交直线
struct Line{point p,v;Line(){}Line(point _p.point _v):p(_p),v(_v){}
}L[N];图形 求垂足 point vp(Line l,point p)//求p点向l做垂线得到的垂足
{double Disdis(l,p);//求p到l的距离Dis DisDis*Dis;double pDis(p-l.p).length();//求AP距离pDis pDispDis*pDis;double vDissqrt(pDis-Dis);//勾股定理得到AH距离 point ansl.pl.v*(vDis/l.v.length());//通过方向单位向量乘长度得到路径加起点得到答案 return ans;
}求两圆交点 先求余弦定理 cosp1反函数 角p1p1p2旋转到p11T方向调整长度p1p1T向量T 代码
point get_intersection(circle A,circle B)
{point ABB.o-A.o;double costhetaAB.length() * AB.length() A.r *A.r-B.r*B.r;costhetacostheta/(2*AB.length()*A.r);//余弦定理ABAB.rotatr(acos(costheta));//旋转theta角return A.oAB*(A.r/AB.length());
} 直线与圆交点 代码
point get_intersection(circle A,Line B)
{point Hvp(B,A.o);//求垂线 double OH(H-A.o).length();double HYsqrt(A.r * A.r -OH * OH);return H B.v *(HY/B.v.length());// return H B.v *(-HY/B.v.length());
}点单位向量 * 长度
多边形问题
平面上n个点收尾顺次连接组成的平面图形 可能是凸多边形或者凹多边形
判断一个点是否在任意多边形内部
从这个点出发引一条射线如果这个射线与多边形有奇数个交点则在内部否则在外部
double calc_S()
{double ans0;int npoly.size();for(int i1;in;i)anspoly[i-1]^poly[i];anspoly[n-1]^poly[0];return ans/2;
}Pick定理
对于顶点都是整点的多边形设其面积为S多边形内部的点数为a边上的点数为b那么满足 S a b/2 - 1
凸包
给出一个二维平面内的点集如果任意两个点的连线都在点集内则这个点集是个凸集 对于给定的散点集X包含X的所有凸集的交集S叫做X的凸包 点就是墙上的钉子用一个橡皮筋套在外面收缩后形成的凸多边形就是凸包
求点集的凸包
水平法
凸包一般使用水平法求解 将凸包分为上凸壳和下凸壳两部分分别求解 每一部分按照x的坐标排序用单调栈维护利用叉积的符号判断凹凸性
增量法 判断情况 此时B合法 此时B不合法 不合法的点一定是最后添加入S的且是连续的
//判断上凸包
sort(poly.begin(),poly.end(),cmp);
int top0,npoly.size();
Stack[top]poly[0];
for(int i1;in;i)
{point Cpoly[i];while(top1){point BStack[top];point AStack[top-1];point ABB-A;point ACC-A;if((AB^AC)eps)top--;else break;}Stack[top]C;
}半平面
• 顾名思义就是平面的一半。一条直线会把平面分成两部分就 是两个半平面。对于半平面我们可以用直线方程式如 axbyc 0 表示更常用的是用直线表示
半平面交
• 顾名思义就是多个半平面求交集。其结果可能是一个凸多边形、 无穷平面、直线、线段、点等。 • 什么时候需要半平面交 • 1. 二维线性规划 高中数学 • 2. 求多边形的核 • 多边形的核如果多边形中存在一个区域使得在区域中可以看到 多边形中任意位置反之亦然则这个区域就是多边形的核
求半平面交
• 理论上有很多很多种求法但是在实际应用中效率最高而且最好 写的是 SI 增量法也就是一个一个插入半平面并且更新答案。 • 核心思想 • 1. 选取逆时针方向为正方向把所有的直线变成向量。 • 2. 所有的向量按照极角排序角度相同的保留左边的。 • 3. 按照顺序每次插入一个平面删掉右面的部分保留左边的部 分。 ###具体方法 1.选方向排序如上文 • 2.用双端队列保存构成当前核的所有向量。 • 3.按照顺序遍历所有向量每次加入判断影响 • 假设队列中最后两条直线的交点是左图所示。如果新加入了直线 后原来的交点在直线右侧说明最后一条直线没有用把它从队 列中删除。 看遍边6要不要保留就看5和6的交点在直线的哪一侧
由p指向v的向量 ans存的交点 q存的边
