公司建设网站价格wordpress 文章置顶

公司建设网站价格,wordpress 文章置顶,做网站安阳,建一个网站需要什么流程问题重述 给定一个凸多边形#xff08;岛屿的地图#xff09;#xff0c;我们需要找到多边形内部一点#xff0c;使得该点到多边形边界#xff08;即大海#xff09;的最短距离最大。 换句话说#xff0c;就是要求这个凸多边形内最大内切圆的半径。 问题分析 这个问题可…问题重述给定一个凸多边形岛屿的地图我们需要找到多边形内部一点使得该点到多边形边界即大海的最短距离最大。 换句话说就是要求这个凸多边形内最大内切圆的半径。问题分析这个问题可以转化为一个最优化问题我们希望找到一个点PPP使得它到所有边直线的距离的最小值最大。 形式化地就是求max⁡P∈Polygonmin⁡idistance(P,Edgei) \max_{P \in \texttt{Polygon}} \min_{i} \texttt{distance}(P, \text{Edge}_i)P∈Polygonmax​imin​distance(P,Edgei​)其中distance(P,Edgei)\texttt{distance}(P, \texttt{Edge}_i)distance(P,Edgei​)是点PPP到第iii条边所在直线的有向距离。直接求解这个最值问题比较困难。 一个关键的观察是如果我们能猜到这个最大距离的值ddd那么我们可以验证它是否可行。解题思路 二分答案 半平面交1. 二分答案我们最终要求的答案是一个距离rrr。 显然rrr的范围是[0,R][0, R][0,R]其中RRR是多边形的一个特征长度例如最长边的一半。 由于坐标范围是[0,10000][0, 10000][0,10000]我们可以保守地将二分上界定为200002000020000。我们可以对rrr进行二分搜索。 对于每次猜测的中间值midmidmid 我们检查是否存在一个点PPP使得它到每条边的距离都至少为midmidmid。 如果可以说明midmidmid是可行的我们就可以尝试更大的值收缩左边界 如果不可以说明midmidmid太大了我们需要尝试更小的值收缩右边界。2. 如何验证距离ddd是否可行对于一个给定的距离ddd “存在一个点PPP到所有边的距离≥d\ge d≥d” 这个条件 等价于将多边形的每条边向内朝向多边形中心平移距离ddd后 这些新的半平面平移后直线的左侧区域的交集非空。为什么是向内平移因为多边形是逆时针给出的 每条边的“左侧”就是多边形的内部。 要保证点PPP到该边的距离至少为dddPPP必须位于这条边向内平移ddd后形成的新直线的左侧。平移操作 对于一条边AB→\overrightarrow{AB}AB 其方向向量为v⃗B−A\vec{v} B - AvB−A。 一个垂直于v⃗\vec{v}v且指向多边形内部的法向量n⃗\vec{n}n可以通过n⃗(−vy,vx)\vec{n} (-v_y, v_x)n(−vy​,vx​)获得因为逆时针顺序。 将n⃗\vec{n}n单位化后 边ABABAB对应的新直线就是过点An⃗∗dA \vec{n} * dAn∗d且方向为v⃗\vec{v}v的直线。可行性判断 对平移后所有边对应的半平面新直线的左侧区域求交集。 如果交集一个凸多边形区域非空 则ddd可行 如果交集为空 则ddd不可行。3. 算法步骤总结读入凸多边形的顶点。初始化二分边界left 0,right 20000。Whileright - left EPS例如10−810^{-8}10−8mid (left right) / 2。根据mid构造向内缩进的所有半平面。调用半平面交算法计算这些半平面的交集。If交集非空 说明mid可行left mid。Else 说明mid太大right mid。输出left即满足条件的最大距离rrr。时间复杂度 半平面交的复杂度为O(nlog⁡n)O(n \log n)O(nlogn) 其中nnn是顶点数n≤100n \le 100n≤100。 二分次数约log⁡2(20000EPS)≈50\log_2(\frac{20000}{EPS}) \approx 50log2​(EPS20000​)≈50次。 总体计算量很小。关键点与细节凸性保证 题目保证输入是凸多边形这简化了问题。 对于凸多边形 向内缩进后形成的半平面交仍然是一个凸多边形或空集 并且半平面交算法更稳定。精度控制 题目要求误差不超过10−510^{-5}10−5。 在二分和几何运算中使用10−810^{-8}10−8的EPS可以保证精度。半平面交算法 这是本体的核心。 算法步骤通常为将所有半平面直线按极角排序。使用双端队列维护可能构成最终交集的半平面。不断检查队首/队尾的半平面是否冗余即其与新加入半平面的交点不在当前半平面内。最后检查队首和队尾的半平面是否矛盾。计算队列中相邻半平面的交点 得到最终交集多边形的顶点。参考代码// Most Distant Point from the Sea// UVa ID: 1396// Verdict: Accepted// Submission Date: 2025-12-15// UVa Run Time: 0.000s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constdoubleEPS1e-8;// 精度控制constdoubleINF1e10;// 无穷大// 点与向量structPoint{doublex,y;Point(doublex0,doubley0):x(x),y(y){}Pointoperator(constPointb)const{returnPoint(xb.x,yb.y);}Pointoperator-(constPointb)const{returnPoint(x-b.x,y-b.y);}Pointoperator*(doublek)const{returnPoint(x*k,y*k);}Pointoperator/(doublek)const{returnPoint(x/k,y/k);}doubledot(constPointb)const{returnx*b.xy*b.y;}doublecross(constPointb)const{returnx*b.y-y*b.x;}doublelength()const{returnsqrt(x*xy*y);}Pointnormal()const{returnPoint(-y,x);}// 逆时针旋转90度法向量};// 直线/半平面点p方向向量v左侧为半平面structLine{Point p,v;doubleangle;Line(){}Line(Point p,Point v):p(p),v(v){angleatan2(v.y,v.x);}booloperator(constLineb)const{returnangleb.angle;}Pointintersect(constLineb)const{Point up-b.p;doubletb.v.cross(u)/v.cross(b.v);returnpv*t;}boolonLeft(Point pt)const{returnv.cross(pt-p)EPS;}// 点在半平面左侧严格};// 半平面交返回多边形点集若为空表示无解vectorPointhalfplaneIntersection(vectorLinelines){intnlines.size();sort(lines.begin(),lines.end());intfirst0,last0;vectorPointp(n);vectorLineq(n);q[0]lines[0];for(inti1;in;i){while(firstlast!lines[i].onLeft(p[last-1]))last--;while(firstlast!lines[i].onLeft(p[first]))first;q[last]lines[i];if(fabs(q[last].v.cross(q[last-1].v))EPS){// 平行last--;if(q[last].onLeft(lines[i].p))q[last]lines[i];}if(firstlast)p[last-1]q[last-1].intersect(q[last]);}while(firstlast!q[first].onLeft(p[last-1]))last--;if(last-first1)returnvectorPoint();// 空集p[last]q[last].intersect(q[first]);vectorPointres;for(intifirst;ilast;i)res.push_back(p[i]);returnres;}intmain(){intn;while(cinnn){vectorPointpoly(n);for(inti0;in;i)cinpoly[i].xpoly[i].y;doubleleft0,right20000;// 最大距离不超过坐标范围while(right-leftEPS){doublemid(leftright)/2;vectorLinelines;// 构造向内缩进mid的半平面for(inti0;in;i){Point apoly[i],bpoly[(i1)%n];Point dirb-a;Point normalPoint(-dir.y,dir.x);// 法向量指向多边形内部因为顶点逆时针normalnormal/normal.length();// 单位化lines.push_back(Line(anormal*mid,dir));// 边向内平移mid}vectorPointreshalfplaneIntersection(lines);if(res.empty())rightmid;// 无解距离太大elseleftmid;// 有解可以尝试更大距离}printf(%.6lf\n,left);// 输出左端点满足条件}return0;}总结本题是一个经典的几何最优化问题 通过二分答案将最优化问题转化为判定性问题 再利用半平面交这一强大的几何工具进行判定。 题目融合了二分搜索、 计算几何向量运算、 直线表示、 半平面交等多个知识点 是一道非常好的综合练习题。 掌握半平面交算法是解决此类问题的关键。