企业官网建设流程全解析

asp手机网站源码下载,wordpress文章表单,网站的制作过程,wordpress中文界面问题描述 题目定义了一类“凹凸不平的物体”#xff08;Bumpy Objects\texttt{Bumpy Objects}Bumpy Objects#xff09;。每个物体由一个多边形表示#xff0c;已知其质心坐标和按逆时针顺序排列的顶点坐标。 一个物体能够稳定旋转站立的条件是#xff1a;存在两个顶点Bumpy Objects\texttt{Bumpy Objects}Bumpy Objects。每个物体由一个多边形表示已知其质心坐标和按逆时针顺序排列的顶点坐标。一个物体能够稳定旋转站立的条件是存在两个顶点可以用一条不与物体相交的直线将它们连接起来并且当这条直线水平时质心位于该直线上方且严格位于两个端点的投影之间。满足上述条件的这条直线称为物体的基线base line\texttt{base line}base line。一个物体通常有多个稳定位置对应多条基线。每条基线由其接触到的编号最大的顶点来标识顶点编号从111开始按逆时针顺序递增。题目要求对于给定的物体找到所有稳定位置中基线标识号最小的那个位置并输出其基线标识号。输入包含多个数据集每个数据集包含一个长度小于202020的字符串表示物体名称。两个整数表示质心的坐标。多对整数表示多边形顶点的坐标以0 0结束。所有数据集以单个#结束。输出对于每个物体输出其名称和满足条件的最小基线标识号。题目分析与建模关键条件解读基线定义基线是连接两个顶点的线段且线段本身不与多边形相交即是多边形的一条“支撑弦”。稳定条件当这条线段被放置为水平时质心必须在它的正上方。质心在水平方向上的投影必须严格位于线段两个端点的投影之间即不能与端点重合。基线标识由线段接触到的编号最大的顶点决定。因此我们需要记录每个顶点的原始输入编号。核心难点与突破口几何搜索范围一个凹多边形的潜在基线数量可能很多任意两个顶点都可能。但是根据物理直觉和几何性质只有凸包Convex Hull\texttt{Convex Hull}Convex Hull上的边或弦才有可能成为有效的基线。为什么如果一条边在凸包内部那么它必然与多边形自身相交因为它穿过了多边形的“内部”这违反了基线“不与物体相交”的条件。因此所有有效的基线其两个端点必然是多边形凸包的顶点。更进一步基线本身必须是凸包的一条边或者是凸包的一条弦连接两个非相邻凸包顶点的线段。稳定条件判定对于一个候选的基线(A,B)(A, B)(A,B)设其被旋转至水平。要判断质心CCC是否在其上方且投影严格在A,BA, BA,B之间可以等价于判断以下两个条件在原始坐标系下上方性质心CCC位于有向直线ABABAB的左侧假设顶点是逆时针排列那么多边形内部在每条边的左侧。用叉积判断(B−A)×(C−A)0(B-A) \times (C-A) 0(B−A)×(C−A)0。投影在内部这等价于角∠ACB\angle ACB∠ACB和∠BCA\angle BCA∠BCA都是锐角。如果质心投影在线段端点之外那么其中一个角将是钝角或直角当投影与端点重合时。因此我们可以通过余弦定理a2b2c2a^2 b^2 c^2a2b2c2来判断一个角是否为锐角。算法思路输入与存储读入物体名称和质心坐标。读入所有顶点并记录其原始输入序号从 1 开始。求凸包使用Andrew\texttt{Andrew}Andrew算法或称单调链算法求出所有顶点的凸包。该算法能O(nlog⁡n)O(n \log n)O(nlogn)时间内得到按逆时针顺序排列的凸包顶点序列。枚举候选基线遍历凸包上的所有边相邻顶点对。根据分析只需检查凸包的边。对于凸包的边(Vi,Vi1)(V_i, V_{i1})(Vi​,Vi1​)检查它是否可能是一条有效基线条件111质心CCC是否位于该边的左侧cw(V_i, V_{i1}, C)为true。注意代码中的cw函数clockwise\texttt{clockwise}clockwise判断点是否在向量右侧由于顶点是逆时针的多边形内部在左侧所以这里判断质心在右侧即从多边形的“外部”看质心在边的上方。这与分析中的“左侧”是等价的只是坐标系和判断函数实现的差异。条件222333角∠(C,Vi,Vi1)\angle (C, V_i, V_{i1})∠(C,Vi​,Vi1​)和角∠(C,Vi1,Vi)\angle (C, V_{i1}, V_i)∠(C,Vi1​,Vi​)是否都是锐角isAcuteAngle函数。计算基线标识并更新如果当前凸包的边满足以上三个条件那么它就是一个稳定位置对应的基线。这条基线接触到的顶点是ViV_iVi​和Vi1V_{i1}Vi1​。根据题目定义该基线的标识号为这两个顶点原始编号的较大值。我们需要在所有满足条件的基线中找到这个标识号的最小值。输出结果输出物体名称和找到的最小基线标识号。复杂度分析时间复杂度凸包计算O(nlog⁡n)O(n \log n)O(nlogn)其中nnn为顶点数。凸包边枚举与条件判断O(n)O(n)O(n)。总体复杂度为O(nlog⁡n)O(n \log n)O(nlogn)对于n≤100n \leq 100n≤100的数据范围非常高效。空间复杂度O(n)O(n)O(n)用于存储顶点和凸包。代码实现// Bumpy Objects// UVa ID: 132// Verdict: Accepted// Submission Date: 2015-12-11// UVa Run Time: 0.000s//// 版权所有C2015邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;#defineMAX_VERTICES105#defineEPSILON1E-10structpoint{intx;inty;intindex;// 顶点的原始编号};structpolygon{intnumber;// 顶点数point vertex[MAX_VERTICES];// 顶点数组};// 计算叉积 (c - a) x (b - a)intcrossProduct(point a,point b,point c){return(c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);}// 判断点 c 是否在向量 ab 的顺时针方向右侧boolcw(point a,point b,point c){returncrossProduct(a,b,c)EPSILON;}// 判断点 c 是否在向量 ab 的逆时针方向左侧boolccw(point a,point b,point c){returncrossProduct(a,b,c)-EPSILON;}// 判断三点是否共线boolcollinear(point a,point b,point c){returnfabs(crossProduct(a,b,c))EPSILON;}// 判断点 c 在向量 ab 的左侧或共线boolccwOrCollinear(point a,point b,point c){returnccw(a,b,c)||collinear(a,b,c);}// 排序比较函数先按 y 坐标升序y 相同则按 x 坐标升序boollowerLeft(point a,point b){return(a.yb.y)?(a.xb.x):(a.yb.y);}// Andrew 凸包算法单调链voidandrewConvexHull(point vertex[],intnumber,polygonhull){// 1. 按 lowerLeft 规则排序sort(vertex,vertexnumber,lowerLeft);point upper[MAX_VERTICES],lower[MAX_VERTICES];inttop;// 2. 构造上凸包upper[0]vertex[0];upper[1]vertex[1];top2;for(inti2;inumber;i){upper[top]vertex[i];// 当新点导致上凸包出现“右转”或“直行”时删除栈顶的点while(top2ccwOrCollinear(upper[top-2],upper[top-1],upper[top])){upper[top-1]upper[top];top--;}top;}// 将上凸包的点存入结果 hullhull.number0;for(inti0;itop;i)hull.vertex[hull.number]upper[i];// 3. 构造下凸包lower[0]vertex[number-1];lower[1]vertex[number-2];top2;for(intinumber-3;i0;i--){lower[top]vertex[i];// 同理删除导致“右转”或“直行”的点while(top2ccwOrCollinear(lower[top-2],lower[top-1],lower[top])){lower[top-1]lower[top];top--;}top;}// 将下凸包的点去掉首尾避免重复加入结果 hullfor(inti1;itop-1;i)hull.vertex[hull.number]lower[i];}// 计算两点距离的平方避免开方doubledistances(point a,point b){returnpow(a.x-b.x,2)pow(a.y-b.y,2);}// 根据余弦定理判断角 abc 是否为锐角。// 对于角 ABC边为 a |B-C|, b |A-C|, c |A-B|。// 余弦定理cos(B) (a^2 c^2 - b^2) / (2ac)。// 角 B 为锐角当且仅当 cos(B) 0即 a^2 c^2 - b^2 0。boolisAcuteAngle(point a,point b,point c){doubleAdistances(b,c),Bdistances(a,c),Cdistances(a,b);return(AC-B)0;}// 在凸包中寻找最小基线编号intlowestNumber(polygon pg,point center,intnumber){intminNumbernumber;// 初始化为顶点总数一个上界for(inti0;ipg.number;i){point p1pg.vertex[i];point p2pg.vertex[(i1)%pg.number];// 检查三个条件// 1. 质心在凸包边的“上方”cw 判断// 2. 角 center, p1, p2 是锐角// 3. 角 center, p2, p1 是锐角if(cw(p1,p2,center)isAcuteAngle(p1,p2,center)isAcuteAngle(p2,p1,center)){// 基线标识号为两个端点原始编号的较大值intlineNumbermax(p1.index,p2.index);minNumbermin(minNumber,lineNumber);}}returnminNumber;}intmain(){point tile[MAX_VERTICES],centerOfMass;polygon container;string name;// 循环读取每个物体直到遇到 #while(cinname,name!#){coutname;// 先输出名称cincenterOfMass.xcenterOfMass.y;intx,y,number0;// 读取顶点直到遇到 0 0while(cinxy,x||y){// 存储顶点并记录其原始序号从1开始tile[number](point){x,y,number1};number;}// 计算顶点的凸包andrewConvexHull(tile,number,container);// 在凸包上寻找最小基线标识号并输出cout lowestNumber(container,centerOfMass,number)endl;}return0;}