南京网站建设手机百度网址大全首页

当前位置： 首页 > news >正文

南京网站建设,手机百度网址大全首页,专业网站设计制作改版,网站正能量下载直接进入主页可以吗安全吗参考文章#xff1a;范神的神仙博客 前置芝士 一些高中数学 向量的叉积#xff1a;向量的点积为 a⋅b∣a∣∣b∣cos⁡a,ba\cdot b|a||b|\cosa,ba⋅b∣a∣∣b∣cosa,b#xff0c;向量的叉积为 ab∣a∣∣b∣sin⁡a,ba\times b|a||b|\sin范神的神仙博客 前置芝士 一些高中数学 向量的叉积向量的点积为 a⋅b∣a∣∣b∣cos⁡a,ba\cdot b|a||b|\cosa,ba⋅b∣a∣∣b∣cosa,b向量的叉积为 a×b∣a∣∣b∣sin⁡a,ba\times b|a||b|\sina,ba×b∣a∣∣b∣sina,b在平面直角坐标系中 a(x1,y1),b(x2,y2)a(x_1,y_1),b(x_2,y_2)a(x1​,y1​),b(x2​,y2​)则 a×bx1y2−x2y1a\times bx_1y_2-x_2y_1a×bx1​y2​−x2​y1​。容易发现叉积不满足交换律不要写反。
存储及基本运算 我也不知道为什么到了这就突然不压行了。 struct qwq{//点 double x,y; }; struct qaq{//线 qwq d,a,b;//d为a-b方向的单位向量 }; struct cir{//圆 qwq p;double r;//圆心及半径 }; inline qwq operator (const qwq a,const qwq b){return {a.xb.x,a.yb.y}; } inline qwq operator - (const qwq a,const qwq b){return {a.x-b.x,a.y-b.y}; } inline qwq operator * (const qwq a,const double b){return {a.x*b,a.y*b}; } inline qwq operator / (const qwq a,const double b){return {a.x/b,a.y/b}; } inline double operator * (const qwq a,const qwq b){//点积 return a.x*b.xa.y*b.y; } inline double operator ^ (const qwq a,const qwq b){//叉积 return a.x*b.y-b.x*a.y; } inline double len(qwq a){return sqrt(a.x*a.xa.ya.y); } inline qaq get(qwq a,qwq b){//已知两点构造直线qwq d(b-a)/len(b-a);return {d,a,b}; }点线基本问题 点到直线垂足 求完垂足显然就可以用初中知识求出点到直线距离点关于直线对称点等不一一展开。 inline qwq cz(qaq l,qwq p){return l.al.d((p-l.a)l.d); }点与直线位置关系 用叉积与 000 的大小关系可以判断顺时针/逆时针/在线上。 如果直线是向量那可以进一步用点积判断点在向量上/延长线上/反向延长线上。 if(fabs(l.d^(p-l.a))eps){if(((p-l.a)(p-l.b))eps) puts(ON_SEGMENT);//注意点与端点重合的情况实质上是0else if((l.d*(p-l.a))-eps) puts(ONLINE_BACK);else puts(ONLINE_FRONT);}else{if((l.d^(p-l.a))eps) puts(COUNTER_CLOCKWISE);else puts(CLOCKWISE);}直线与直线位置关系 共线用叉积判断垂直用点积判断。 if(fabs(l1.d^l2.d)eps) puts(2);//共线/平行else if(fabs(l1.d*l2.d)eps) puts(1);//垂直else puts(0);//其它判断两线段是否相交 快速排斥实验定义一条线段占的区域为各边平行坐标轴且以该线段为对角线的矩形。当两个矩形不相交是两线段一定不相交。跨立实验若线段 aaa 两端点在线段 bbb 所在直线两侧且线段 bbb 两端点在线段 aaa 所在直线两侧则通过了跨立实验。 发现通过了这两个实验之一都无法保证两线段相交而将它们结合起来用就是充要条件了。 不要忘了跨立实验有端点在线段上的情况。似乎写的有点丑 inline bool check(qwq p1,qwq p2,qwq p3,qwq p4){//快速排斥实验 if(max(p1.x,p2.x)min(p3.x,p4.x)) return 0;if(max(p3.x,p4.x)min(p1.x,p2.x)) return 0;if(max(p1.y,p2.y)min(p3.y,p4.y)) return 0;if(max(p3.y,p4.y)min(p1.y,p2.y)) return 0;return 1; } inline int side(qwq p,qaq l){//跨立实验 double tmpl.d^(p-l.a);if(fabs(tmp)eps) return 0;if(tmp-eps) return 1;return 2; } inline void solve(){l1get(p1,p2),l2get(p3,p4);if(!check(p1,p2,p3,p4)) puts(0);else{int a1side(p1,l2),a2side(p2,l2),a3side(p3,l1),a4side(p4,l1);if((a1!a2||!a1||!a2)(a3!a4||!a3||!a4)) puts(1);else puts(0); } }求两直线交点 设交点为 ppp则代入第一个直线的方程式得 pa1k⋅d1pa_1k\cdot d_1pa1​k⋅d1​且同时 ppp 要满足在第二条直线上即 (p−a2)×d20(p-a_2)\times d_20(p−a2​)×d2​0联立一下(a1−a2k×d1)×d20(a_1-a_2k\times d_1)\times d_20(a1​−a2​k×d1​)×d2​0叉积拆开即为 k(a2−a1)×d2d1×d2k\dfrac{(a_2-a_1)\times d_2}{d1\times d2}kd1​×d2(a2​−a1​)×d2​​。 inline qwq jd(qaq l1,qaq l2){double k((l2.a-l1.a)^l2.d)/(l1.d^l2.d);return l1.a(l1.d*k); } 求两线段距离 特殊情况是相交答案为 000其余情况就是端点到另一线段距离了我是用垂足在不在线段上来判的似乎又写丑了。 l1get(p1,p2),l2get(p3,p4);if(xj()){puts(0.0000000000);continue;}qwq pcz(p1,l2);double ansmin(dis(p1,p3),min(dis(p1,p4),min(dis(p2,p3),dis(p2,p4)))); if(on(p,l2)) ansmin(ans,dis(p,p1));pcz(p2,l2);if(on(p,l2)) ansmin(ans,dis(p,p2));pcz(p3,l1);if(on(p,l1)) ansmin(ans,dis(p,p3));pcz(p4,l1);if(on(p,l1)) ansmin(ans,dis(p,p4));printf(%.10lf\n,ans);公共投影问题 给定 nnn 条线段求是否存在一条直线使得这些线段在这条直线上的投影有公共点。 问题转化假设存在那么过公共点作直线垂线一定与每条线段都相交。而这条垂线一定可以通过平移使得它经过所有端点中的两个。于是枚举两个端点判断即可。 直线的旋转 向量 (x,y)(x,y)(x,y) 逆时针旋转 θ\thetaθ 度得到的向量为 (xcos⁡θ−ysin⁡θ,ycos⁡θxsin⁡θ)(x\cos\theta-y\sin\theta,y\cos\thetax\sin\theta)(xcosθ−ysinθ,ycosθxsinθ)详见数学必修三。 inline qwq rotate(qwq a,double t){double sisin(t),cocos(t);return {a.x*co-a.y*si,a.y*coa.x*si}; }多边形问题 下面默认所有顶点都按逆时针顺序存储。 求多边形面积 任选一个点把多边形拆成若干三角形即可根据叉积的几何意义计算S12∣∑i1npi×pi%n1∣S\dfrac{1}{2}|\sum\limits{i1}^npi\times p{i\%n1}|S21​∣i1∑n​pi​×pi%n1​∣显然任意点直接取原点是最方便的。 判断凹/凸多边形 忽略相邻三点共线情况凸多边形即相邻两边所成向量之间的叉积正负性始终相同。 p[0]p[n],p[n1]p[1];int pre0;rep(i,1,n){double tmp(p[i1]-p[i])^(p[i]-p[i-1]);if(fabs(tmp)eps) continue;int now(tmpeps)?1:-1;if(!pre) prenow;else if(pre!now) return puts(0),0;}判断一个点是否在多边形内 这里是回转数算法。 把待判断的点 aaa 与多边形每一个顶点依次相连相邻顶点之间会形成若干有方向的夹角。画图得知当且仅当这些夹角和为 000 时点在多边形外部。 注意 epsepseps 不要过小容易炸。 inline bool on(qwq p,qaq l){if(pl.a||pl.b) return 1;double tmp(p-l.a)^l.d;if(fabs(tmp)eps) return 0;return p.xmin(l.a.x,l.b.x)p.xmax(l.a.x,l.b.x)p.ymin(l.a.y,l.b.y)p.ymax(l.a.y,l.b.y); } inline double jiao(qwq a,qwq b){double ansacos(min(1.0,(a^b)/(len(a)*len(b))));//取min是为了避免一些精度误差带来的玄学问题 return ans; } inline bool pd(qaq l,qwq p){//判断正角还是负角return (l.d^(p-l.a))eps; } inline void solve(){double now0;rep(i,1,n){if(on(a,get(p[i],p[i1]))) return puts(1),void();//在多边形上 if(pd(get(a,p[i]),p[i1])) nowjiao(a-p[i],a-p[i1]);else now-jiao(a-p[i],a-p[i1]);}if(fabs(now)eps) puts(0);//在多边形外 else puts(2); }二维凸包 定义包含给定的所有点的周长最小的凸多边形。 求凸包可以用 Andrew 算法在 O(nlog⁡n)O(n\log n)O(nlogn) 的时间内求解。 先把所有点以 xxx 为第一关键字yyy 为第二关键字升序排序。那么排完序的第一个点和最后一个点一定在凸包上且以它们为分界线可以将凸包分为上下两部分而两部分转弯的顺逆时针情况都是相同的。所以可以用单调栈维护先求出下凸壳再在没使用过的点中求出上凸壳。 实现的时候注意因为第一个点要用来更新上凸壳所以开始不能记 vis[1]1vis[1]1vis[1]1最后栈内一定重复加了一个 111所以要 top−−top–top−−。 inline void solve(){sort(a1,an1);s[top]1;rep(i,2,n){while(top1((a[s[top]]-a[s[top-1]])^(a[i]-a[s[top]]))0) vis[s[top]]0,–top;vis[i]1,s[top]i;}int postop;for(int in;i;–i) if(!vis[i]){while(toppos((a[s[top]]-a[s[top-1]])^(a[i]-a[s[top]]))0)vis[s[top]]0,–top;vis[i]1,s[top]i;}–top; }旋转卡壳 常用于求平面上最远点对。 首先显然最远点对的两个点一定都在凸包上而逆时针遍历凸包的每一条边的过程中离当前边所在直线距离最远的点也一定沿着逆时针方向旋转于是维护这个最远点的位置用这个点到当前边两端点的距离更新答案即可。 inline double dis(qwq a,qwq b){double xa.x-b.x,ya.y-b.y;return x*xy*y; } inline double disl(qwq p,qaq l){return fabs(l.d^(p-l.a)); } inline double kk(){p[tot1]p[1],p[0]p[tot],nxt[tot]1;rep(i,1,tot-1) nxt[i]i1;int now2;double ans0;rep(i,1,tot){qaq lget(p[i],p[i1]);while(disl(p[nxt[now]],l)disl(p[now],l)) nownxt[now];ansmax(ans,max(dis(p[i],p[now]),dis(p[i1],p[now])));}return sqrt(ans); }半平面交 顾名思义求解多个凸多边形的面积交问题。 先将所有边进行极角排序即用 atan2(y,x)atan2(y,x)atan2(y,x) 求出 tan⁡αyx,α∈(−π,π]\tan\alpha\dfrac{y}{x},\alpha\in(-\pi,\pi]tanαxy​,α∈(−π,π] 的角 α\alphaα 不同的角按角的大小排序相同的将位置更靠里的放在前面。 然后用一个 dequedequedeque 维护对答案可能有贡献的边及相邻边的交点。具体地每加入一条边先不断从队尾弹出已经不合法的交点再不断从队首弹出已经不合法的交点最后插入当前边已经当前边和之前的队尾的交点。 插入进行到最后时可能队尾的一些点被队首卡掉了而队首的点一直被后来加入的队尾们约束着不可能被卡掉所以要不断弹出队尾直至合法。 最后别忘了加入一下队尾和队首的交点。 构成一个多边形至少要三条边若最终队列长度小于 333说明面积交为 000。 inline bool in(qwq p,qaq l){return (l.d^(p-l.a))eps;} inline bool out(qwq p,qaq l){return (l.d^(p-l.a))-eps;} inline bool cmp(qaq l1,qaq l2){double p1atan2(l1.d.y,l1.d.x),p2atan2(l2.d.y,l2.d.x);if(fabs(p1-p2)eps) return p1p2;return in(l1.a,l2); } inline qwq jiao(qaq l1,qaq l2){double k((l2.a-l1.a)^l2.d)/(l1.d^l2.d);return l1.al1.dk; } inline void half(){sort(a1,atot1,cmp);rep(i,1,tot){if(lrfabs(q[r].d^a[i].d)eps) continue;//判掉无用的平行边while(lrout(jd[r],a[i])) –r;//当队列长为2且唯一交点不合法时先弹出队首会出错必须先弹队尾while(lrout(jd[l1],a[i])) l;//交点是从队首的下一个开始产生的q[r]a[i];if(lr) jd[r]jiao(a[i],q[r-1]);}while(lrout(jd[r],q[l])) –r;if(lr) jd[r1]jiao(q[l],q[r]),r;nr-l;rep(i,1,n) p[i]jd[il];p[n1]p[1]; }圆相关问题 三角形内切圆 求出两条角平分线交点即为圆心。半径即为点到直线距离。 inline qaq pf(qaq l1,qaq l2){//求角平分线qwq d(l1.dl2.d)/len(l1.dl2.d);return {d,l1.a,l1.ad}; } inline cir nqy(qwq p1,qwq p2,qwq p3){cir ans;qaq l1pf(get(p1,p2),get(p1,p3));qaq l2pf(get(p2,p1),get(p2,p3));ans.pjd(l1,l2),ans.rdis(ans.p,get(p1,p2));return ans; }三角形外接圆 求两条中垂线交点即可。 inline qaq zcx(qaq l){//中垂线qwq mid{(l.a.xl.b.x)/2,(l.a.yl.b.y)/2};return {{l.d.y,-l.d.x},mid}; } inline cir wjy(qwq p1,qwq p2,qwq p3){qaq l1zcx(get(p1,p2)),l2zcx(get(p2,p3));qwq pjd(l1,l2);return {p,dis(p,p1)}; }圆和直线交点 在保证有交点的前提下求出圆心到直线垂足后勾股定理即可。 inline void query(qaq l){vectorqwq ans;qwq czl.d(l.d*(c.p-l.a))l.a;double d1len(cz-c.p),d2sqrt(c.r*c.r-d1*d1);ans.push_back(czl.d*d2),ans.push_back(cz-l.d*d2);sort(ans.begin(),ans.end());for(qwq tmp:ans) printf(%.8lf %.8lf ,tmp.x,tmp.y);putchar(\n); }圆与圆交点 发现以两圆心和其中一个交点为顶点的三角形三边均已知就可以用余弦定理求出其中一个角旋转经过两圆心的直线即可。 inline void query(cir c1,cir c2){vectorqwq ans;double dislen(c1.p-c2.p);qaq lget(c1.p,c2.p);double tacos((c1.r*c1.r-c2.r*c2.rdis*dis)/(2*c1.r*dis));qwq d1rotate(l.d,t),d2rotate(l.d,2*pi-t);ans.push_back(c1.pd1*c1.r),ans.push_back(c1.pd2*c1.r);sort(ans.begin(),ans.end());for(qwq tmp:ans) printf(%.8lf %.8lf ,tmp.x,tmp.y);putchar(\n); }过圆外一点作圆的切线 圆外点 ppp圆心和任意切点组成的直角三角形两边已知可以求解其中一锐角并将直线旋转。 inline void query(qwq p,cir c){vectorqwq ans;qaq lget(p,c.p);double dislen(p-c.p),tasin(c.r/dis),dsqrt(dis*dis-c.r*c.r);qwq d1rotate(l.d,t),d2rotate(l.d,pi*2-t);ans.push_back(pd1*d),ans.push_back(pd2*d);sort(ans.begin(),ans.end());for(qwq tmp:ans) printf(%.8lf %.8lf\n,tmp.x,tmp.y); }求两圆公切线 分内含/内切/相交/外切/外离五种情况考虑。也是利用一些简单的几何性质求解直角三角形然后旋转得到交点。 代码求的是在圆 c1c_1c1​ 上的交点。 inline void solve(cir c1,cir c2){int flag0;if(c1.rc2.r) swap(c1,c2),flag1;double dislen(c1.p-c2.p);if(disc2.rc1.r) return;//内含qaq lget(c1.p,c2.p);if(fabs(c1.r-c2.r-dis)eps){//内切qwq ansc1.pl.d*c1.r;return printf(%.10lf %.10lf\n,ans.x,ans.y),void();}vectorqwq ans;double tacos((c1.r-c2.r)/dis);qwq d1rotate(l.d,t),d2rotate(l.d,2*pi-t);if(flag) ans.pb(c2.pd1*c2.r),ans.pb(c2.pd2*c2.r);else ans.pb(c1.pd1*c1.r),ans.pb(c1.pd2*c1.r);if(fabs(dis-c1.r-c2.r)eps) ans.pb(c1.pl.d*c1.r);//外切else if(disc1.rc2.r){//外离if(flag) swap(c1,c2),lget(c1.p,c2.p);double xiedis*c1.r/(c1.rc2.r),tacos(c1.r/xie);d1rotate(l.d,t),d2rotate(l.d,2*pi-t);ans.pb(c1.pd1*c1.r),ans.pb(c1.pd2*c1.r);}sort(ans.begin(),ans.end());for(qwq tmp:ans) printf(%.10lf %.10lf\n,tmp.x,tmp.y); }扇形面积与弓形面积 根据初中公式求解即可。注意这里算的都是圆心角 ≤π\le \pi≤π 的部分的面积。 inline double angle(qwq p1,qwq p2){return acos((p1*p2)/len(p1)/len(p2)); } inline double sshan(cir c,qwq a,qwq b){double tangle(a-c.p,b-c.p);return t/2*c.r*c.r; } inline double sgong(cir c,qwq a,qwq b){return sshan(c,a,b)-fabs((b-c.p)^(a-c.p)/2); }圆与圆面积交 特判内含/外离之后考虑处理相交。发现当圆心角在 π\piπ 以内的时候对答案的贡献为扇形面积减三角形面积否则答案为扇形面积加三角形面积但此时 sin⁡θ\sin\thetasinθ 为负依然正确。 inline double query(cir c1,cir c2){if(c1.rc2.r) swap(c1,c2);double dislen(c1.p-c2.p);if(disc1.rc2.r) return 0;if(c2.rdisc1.r) return pi*c2.r*c2.r;double r1c1.r*c1.r,r2c2.r*c2.r;double t12*acos((dis*disr1-r2)/(2*dis*c1.r));double t22*acos((dis*disr2-r1)/(2*dis*c2.r));return t1/2*r1t2/2*r2-r1*sin(t1)/2-r2sin(t2)/2; }圆与多边形面积交 把多边形拆成多个由多边形上相邻两顶点和圆心组成的三角形根据圆心与多边形的位置关系将每部分面积交标上正负符号然后分类 当前正在讨论的多边形上的两点全在圆内答案为三角形面积 两点全在圆外 两点所成线段与圆没有交点答案为扇形面积两点所成线段与圆有交点答案为扇形面积减多余的弓形面积 一点在圆内一点在圆外答案为一个三角形面积 一个扇形面积。
inline qwq cirline(cir c,qaq l){qwq czl.d((c.p-l.a)*l.d)l.a;double dislen(c.p-cz);return czl.d*sqrt(c.r*c.r-disdis); } inline bool check(qwq a,qwq b,cir c){return max(a.x,b.x)c.p.x-epsmin(a.x,b.x)c.p.xeps||max(a.y,b.y)c.p.y-epsmin(a.y,b.y)c.p.yeps; } inline double calc(cir c,qwq a,qwq b){double tmp(a-c.p)^(b-c.p);if(fabs(tmp)eps) return 0;int ftmp0?1:-1,f1len(a-c.p)c.r,f2len(b-c.p)c.r;if(f1f2) return tmp/2;qaq lget(a,b);qwq czl.d((c.p-l.a)*l.d)l.a;double jllen(c.p-cz);if(jlc.r) tmpsqrt(c.r*c.r-jl*jl);if(!f1!f2){qaq l1get(c.p,a),l2get(c.p,b);double ssshan(c,l1.al1.d*c.r,l2.al2.d*c.r);if(jlc.rcheck(a,b,c)) s-sgong(c,cz-l.d*tmp,czl.d*tmp);return s*f;}if(!f1) swap(a,b),lget(a,b);qwq p1cirline(c,l),p2cirline(c,get(c.p,b));double sfabs((c.p-a)^(p1-a)/2)sshan(c,p1,p2);return s*f; } inline double query(){a[n1]a[1];double ans0;rep(i,1,n) anscalc(c,a[i],a[i1]);return fabs(ans); }杂项 曼哈顿距离与切比雪夫距离 平面上两点 (x1,y1)(x_1,y_1)(x1​,y1​) 和 (x2,y2)(x_2,y_2)(x2​,y2​)它们的曼哈顿距离为 ∣x1−x2∣∣y1−y2∣|x_1-x_2||y_1-y_2|∣x1​−x2​∣∣y1​−y2​∣切比雪夫距离为 max⁡(∣x1−x2∣,∣y1−y2∣)\max(|x_1-x_2|,|y_1-y_2|)max(∣x1​−x2​∣,∣y1​−y2​∣)。 曼哈顿距离 ⇒\Rightarrow⇒ 切比雪夫距离(x,y)⇒(xy,x−y)(x,y)\Rightarrow(xy,x-y)(x,y)⇒(xy,x−y)切比雪夫距离 ⇒\Rightarrow⇒ 曼哈顿距离(x,y)⇒(xy2,x−y2)(x,y)\Rightarrow(\dfrac{xy}{2},\dfrac{x-y}{2})(x,y)⇒(2xy​,2x−y​)。