国家集训队作业poi9809解题报告

1、POI9809 解题题目简述题目中给出了一个多边形，它的内部（不包括边）被红色。还有一个长方形的窗口。问：通过这个窗口，可以看到几块分开的红色多边形？算法分析把题目中给出的多边形称为原多边形来考虑从窗口中可以看到的一块红色多边形。它的每一条边都是原多边形的边的一部分或者长方形的边的一部分。所以，整个一块多边形的是一段长方形的边、一段原多边形的边、一段长方形的边、一段原多边形的边这样相间隔的。它们的分隔点就是原多边形与长方形的交点。把原多边形与长方形的交点简称为交点。那么一段原多边形的边的两端的两个交点在原多边形的边界上一定是相邻的两个交点，如图中的(7,1)和(1,5)；一段长方形的边的两端的

2、两个交点在长方形的边界上也一定是相邻的两个交点，如图中的(5,1)和(7,1)。对于交点，须做一个更严格的界定。对于原多边形上的一条边：如果它的一端在长方形外（包括边界），一端在长方形内（不包括边界），那么它和长方形相交了一次；如果它的两端都在长方形外（包括边界），中间有一段在长方形内部（不包括边界），那么它和长方形相交了两次。图中的(0,1)(0,5),(3,5)和(4,5)都不是交点。所有的交点又可以分成两类：入交点和出交点。逆时针方向遍历原多边形，那些从内往外与长方形的边相交的交点就称为出交点，如(7,5)，而从外往内与长方形的边相交的交点就称为入交点，如(5,5)。逆时针方向遍历的红色

3、多边形，入交点和出交点一定是间隔出现的。入交点和出交点之间一定是一段原多边形上的边，如(7,1)和(1,5)，出交点与入交点之间一定是一段长方形上的边，如(1,5)和 (4,1)。先要找到所有的交点，然后分别求出它们在长方形和原多边形上的顺序。这样，对于每一块可以看到的红色多边形，只要知道它的一个交点，就可以找到它所有的交点。只要把每一个交点都一遍，就得到了。最后，还要考虑三种没有交点的特殊情况：多边形完全在正方形内部正方形完全在多边形内部正方形与多边形相互分离程序实现不需要保存原多边形的顶点，只需要存它们的交点。由于原多边形的边数不超过 5000，所以交点的个数也不超过 5000。每读入原多

4、边形的一条边，就找这条边上的交点。把这些交点顺序保存下来，就得到了交点在原多边形上的顺序（逆时针方向）。另一方面，从长方形的左下角开始逆时针给长方形边上的每一个整点标号。对于每一个找到的交点，可以计算出它所在的点的标号。向）。只要把这些标号排一个序，就得到了交点在长方形上的顺序（逆时针方先找到一个未过的入交点a1，找到在原多边形上 a1 的逆时针方向的下一个交点 b1，再找长方形上 b1 的逆时针方向的下一个交点 a2，再找原多边形上 a2的逆时针方向的下一个交点b2，再找长方形上 b2的逆时针方向的下一个交点过了，可以看到的红色多边a3 ，直到某个ak =a1。以上这些交点就都被形的个数也增

5、加一。如果交点的个数是 0，那么就是特殊情况。如果原多边形的第一个顶点在长方形的内部，那么原多边形一定被完全包含在正方形内部， 是 1。如果原多边形的第一个顶点不在长方形的内部，那么以长方形的左下角为端点向右上方作一条斜率为sqrt(2)的射线。如果它和多边形相交奇数次，那么正方形被完全包含在原多边形内部，是 1，否方形与原多边形相互分离，是 0。算法复杂度由于每一个交点只被遍历一次，所以遍历交点的时间复杂度是 O(t) (t 表示交点的个数)。但是还要进行一次排序，所以这个程序的时间复杂度为 O(t*lgt)。由于t=5000，所以这个复杂度是很低的。空间需求也不是很大，只需要需要 45k。

6、交点的两个顺序和是否已标记。总共附录：源程序varx1,y1,x2,y2,x,y,bx,by,x3,y3:long;i,j,k,n,t,ans:eger;ans 可以看到的红色多边形个数a:array1.5000 of long; loc,order:array1.5001 oflocorderI=I,orderlocI=I visit:array1.5000 of交点所在的点的标号eger;order 长方形上逆时针方向上交点的序号；;是否已标记c:eger;r1:real;procedure check(lx,ly,x,y: beginif lx=xeger);检查边(lx,ly)(x,y

7、)与长方形是否有交点then if (x1x)and(xx2)then if lyythen beginif (lyy1) then begin inc(t);at:=x-x1 end;if (ly=y2) then begin inc(t);at:=x2-x1+y2-y1+x2-x endend else beginif (y=y2) then begin inc(t);at:=x2-x1+y2-y1+x2-x end;if (yy1) then begin inc(t);at:=x-x1 endendelseelse if (y1y)and(yy2)then if lxxthen begi

8、nif (lxx1) then begin inc(t);at:=(x2-x1)*2+y2-y1+y2-yend;if (lx=x2) then begin inc(t);at:=x2-x1+y-y1 endend else beginif (x=x2) then begin inc(t);at:=x2-x1+y-y1 end;if (xx1) then begin inc(t);at:=(x2-x1)*2+y2-y1+y2-y endendelse ;if (c=0)and(t=0) then如果当前交点数是 0，且不是第一种特殊情况，判断这条边是否与射线相交if lx=xthen if x

9、x1then beginr1:=y1+sqrt(2)*(x-x1);if (r1ly)and(r1y)and(r1y1then beginr1:=x1+(y-y1)/sqrt(2);if (r1lx)and(r1x)and(r1lx) then inc(k) endend;procedure qsort(p,q: begineger);对交点在长方形边上的位置排序i:=random(q-p+1)+p; k:=orderi;orderi:=ord i:=p;j:=q;while ij do beginwhile (ij)and(ak=aorderj) do dec(j); orderi:=ord

10、erj;while (i=aorderi) orderj:=orderiend;nc(i);orderi:=k;if pi+1 then qsort(i+1,q)end; beginassign(input,okn.in); reset(input); readln(x1,y2,x2,y1); readln(n); readln(x,y);t:=0;if (x1x)and(xx2)and(y1y)and(yy2) then c:=1 else c:=0;判断原多边形的第一个点在长方形的内部(c=1)还是外部(c=0) k:=0;射线与原多边形交点个数初始化bx:=x;by:=y;for i:=

11、1 to n-1 do begin x3:=x;y3:=y;readln(x,y); check(x3,y3,x,y);end; check(x,y,bx,by); close(input);if t=0then if (c=1)or odd(k)处理特殊情况 then ans:=1else ans:=0 else beginfor i:=1 to t do orderi:=i;qsort(1,t);计算交点在长方形上的逆时针顺序 for i:=1 to t do locorderi:=i; ordert+1:=order1;fillchar(visit,sizeof(visit),false);是否已 ans:=0;标志初始化for i:=1 to t doif odd(i+c) and not(visiti) then begin找一个尚未 j:=i;repeatj:=j mod t+1;的入交点找到它在原多边形上逆时针方向的下一个交点visitj: