1简单多边形.doc

1.简单多边形 p被称做星形多边形(star-shaped), 如果其中存在某个点q,使得对于该多边形内的任何点P, 线段pq完全落在p内. 给出一个算法,判断任何给定的简单多边形是否为一个星形多边形. 该算法的期望运行时间必须是线性的.判定方法是先将所有边两两求出交点，然后依次判断这些交点是不是中点，只要有一个是，多边形就是星形多边形，否则就不是。因为可以证明，只要是星形多边形，这些交点中至少有一个一定是其中点。判断P点是否是中点的方法是：所有顶点与P点之间连一条线，若有连线不全在多变形内，则不是中点。这个问题又可以转化为按一定的顺序（顺时针或逆时针）遍历每条边，看P点是否在所有边的同一侧（右侧或左侧），是的话，P就是中点。源程序如下（POJ3130）：#include #include #define SIZE 110const double Z = 1e-6;struct Linedouble A,B;bool y;lineSIZE;struct Pointdouble x,y;inSIZE,testSIZE*SIZE;int pnum,n;void makepoint(Line &a, Line &b)if(!a.y & !b.y) return ;if(!a.y) testpnum.x = a.A; testpnum+.y = b.A*a.A+b.B;else if(!b.y) testpnum.x = b.A; testpnum+.y = a.A*b.A+a.B;else if(a.A != b.A) testpnum.x = (b.B-a.B)/(a.A-b.A); testpnum.y = testpnum.x*b.A + b.B; pnum+; double crossMul(Point a, Point b,Point c)b.y -= a.y; b.x -= a.x;c.y -= a.y; c.x -= a.x;return b.x*c.y-b.y*c.x;bool check(Point p)int i;double temp,flg = 0;for(i = 0; i n; i+) temp = crossMul(ini,in(i+1)%n,p); if(fabs(temp) Z) temp = 0.0; if(flg = 0) flg = temp; else if(flg*temp 0) return false;return true;int main()int i,j;while(scanf(%d,&n) & n) for(i = 0; i n; i+) scanf(%lf%lf,&ini.x,&ini.y); linei.y = true; for(i = 1;i n; i+) if(ini.x = ini-1.x) linei.y = false; linei.A = ini.x; else linei.A = (ini.y-ini-1.y)*1.0/(ini.x-ini-1.x); linei.B = ini-1.y - linei.A*ini-1.x; if(inn-1.x = in0.x) line0.y = false; line0.A = in0.x; else line0.A = (in0.y-inn-1.y)*1.0/(in0.x-inn-1.x); line0.B = inn-1.y - line0.A*inn-1.x; pnum = 0; for(i = 0; i n; i+) for(j = i+1; j n; j+) makepoint(linei,linej); for(i = 0; i pnum; i+) if(check(testi) break; if(i pnum) printf(1n); else printf(0n);return 0;2. 给出两个x-单调的多边形链P 和 Q . 证明P 和 Q能够相交 O(n), (n是P 和 Q 的顶点的总数). 遍历两个多边形链，直至某一个链中的顶点落入另一个链两个相邻顶点之间。假设P的顶点X坐标在Q的相邻两个顶点（q1,q2）（q1q2的第一个点。判定是否相交。如果不相交，继续遍历。3. 将某凸多边形各边所对应的n条(未排序的)线段组成一个集合E.试给出一个算法,在O(nlogn)时间内,根据 E 计算出该多边形所有顶点按顺时针方向的一个序列.(1)找一个内点(2)计算这个内点到各顶点的角度0-360度(3)按角度排序找一个内点：任选3点x1,y1,x2,y2,x3,y3计算： x0=(x1 + x2 + x3)/3 y0=(y1 + y2 + y3)/3.计算这个内点到各顶点的角度：dy=yi-y0dx=xi-x0ds=sqrt(dx*dx+dy*dy)sin(Ai) = dy/ds判断象限。排序不用说了吧。4.在一个所谓的 “矩形多边形” (recti