信息学集训队作业ural竞赛

1、题目来源Ural 1616 Square Country 4问题描述给出一个平面网格图，中心(0,0)，坐标范围-n,n，给出每一个 1*1 的格子的归属，求将坐标顺时针转后，新格子中用有超过一般土地权的人拥有土地，若没有人超过一般，归国家所有。求坐标旋转以后的归属。算法考虑每个新格子由哪些原先的格子组成，分别求出在新格子中所占的面积。算法证明基本模拟，无需证明。算法实现分析每个新格子由哪些原先的格子组成时，可计算新格子的中心，对应到原先坐标，则所在格子及周围一圈共 9 个有可能有关。求两个相等的正方形的并有很多种方法，我选用了求一般两凸多边形的并的方法。源代码const maxn=100;

2、zero=1e-5;typenumber=extended;po=record x,y:number; end;line=record a,b:po; end;polygon=array1.maxnof po; / Pos are suped in Cclockorderline_set=array1.maxnof line;N_set=array1.maxnof long;Ppo=po;Pline=line; Ppolygon=polygon; PN_set=N_set;Pline_set=line_set;const O:po=(x:0;y:0); Paway:po=(x:52408.2;

3、y:-131401);var a:Ppolygon; a_in:polygon; q:PN_set;:N_set; m_in:line_set;function F_cross(a,b,c:Ppobegin):;F_cross:=(a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x)-zero;P_po(a,b:Ppo):number;:=a.x*b.x+a.y*b.y;disPP(a,b:Ppo):number;var s:number; begins:=sqr(a.x-b.x)+sqr(a.y-b.y);if szero then disPP:=0 else dis

4、PP:=sqrt(s); end;function disPL(a:Ppo var s:number;begin;l:Pline):number;s:=P_cross(l.b,a,l.a);if abs(s)-zero then exit(false);if F_cross(d,a,c) xor F_cross(d,b,c) then begin x.x:=(d.x*s1-c.x*s2)/(s1-s2);x.y:=(d.y*s1-c.y*s2)/(s1-s2); exit(true);end;P_end;er:=false;function A_er(a,b,c,po):;var s1,s2:

5、number; begins1:=P_cross(b,c,a); s2:=P_cross(b,d,a); if abs(s1-s2)=r then exit;);/ sort for a:Ppolygon; q:PN_set;i:=l; j:=r; x:=aqrandom(r-l+1)+l; while i=j do beginwhile (i=j)and not F_cross(aqi,x,O) while (i=j)and not F_cross(x,aqj,O) if i=j then begink:=qi; qi:=qj; qj:=k; inc(i); dec(j);end; end;

6、Qsort(l,j); Qsort(i,r); end;nc(i);do dec(j);function:Ppolygon;n:eger;d:PN_set):long;var i,j,h:longbegin;if n=1 then begin d1:=1; exit; end;if n=2 then begin d1:=1; d2:=2; exit; end; j:=n; a:=a_in;for i:=1 to n-1 doif (mi.xmj.x-zero)or(abs(mi.x-mj.x)zero)and(mi.y2 do(aqi,adh,O,adh) thendh:=qi;if F_cr

7、oss(adh-1,adh,adh-2)then begin dec(h); dh:=dh+1; end else break;end;inc(h); dh:=j; CH:=h; end;procedure Sort_Half(M:Ppolygon;n:long;d:PN_set);var i:longbegin;a:=M; q:=d; for i:=1 to n do qi:=i; Qsort(1,n);end;procedure Sort_Whole(M:Ppolygon;n:long;d:PN_set);var i,j,k:longbegin;a:=M; q:=d; j:=1; k:=n

8、; for i:=1 to n doif (ai.xzero) or(abs(ai.x)zero) then begin qj:=i; inc(j); endelse begin qk:=i; dec(k); end; Qsort(1,k); Qsort(j,n);end;functioner_HP(M:Pline_set;n:long;R:Ppolygon):long;var i,j,k,op,cl:longbegin; h:N_set; x,y:Po;umber;oolean;if nzero then exit(0);ithen beginA_er(Mhop.a,Mhop.b,Mj.a,

9、Mj.b,x);if F_poend;(y,x,ahop,O) then continue;if abs(ss)op do begink:=hcl;if F_cross(ak,aj,O) then exit(0);if A_er(Mj.a,Mj.b,Mk.a,Mk.b,rcl) thenif F_po(rcl,rcl-1,Mk.a,Mk.b)then begin hcl:=0; dec(cl) end else break;end;if op=cl then begink:=hcl;if not F_cross(aj,ak,O) then exit(0);A_er(Mj.a,Mj.b,Mk.a

10、,Mk.b,rcl);inc(cl); hcl:=j; endelse begin inc(cl); hcl:=j; end;if not F_cross(ahcl,ahop,O) then begin ff:=true;repeatA_er(Mhop.a,Mhop.b,Mhcl.a,Mhcl.b,x);if F_po(x,rop,ahop,O)then inc(op)else break;until y:=x;end; end;if not fffor i:=opfalse;then exit(0);to cl do ri-op+1:=ri;A_er(Mhop.a,Mhop.b,Mhcl.a

11、,Mhcl.b,rcl-op+1);exit(cl-op+1);end;function var i:long beginfor i:=1er_CP(a,b:Ppolygon;n,m:long;c:Ppolygon):long;to n-1 do beg_ini.a:=ai; m_ini.b:=ai+1; end;m_inn.a:=an; m_inn.b:=a1;for i:=1 to m-1 do beg_inn+i.a:=bi; m_inn+i.b:=bi+1; end;m_inn+m.a:=bm; m_inn+m.b:=b1;exit(end;er_HP(m_in,n+m,c);cons

12、t dx:array1.9of longdy:array1.9of long=(-1,-1,-1,0,0,0,1,1,1);=(-1,0,1,-1,0,1,-1,0,1);var n,i,j,k,ii,jj:long; st:array-30.30of string; p1,p2,p0:polygon; cosa,sina,alfa,x,y:number;ch:char;flag:;ans:arraya.zof number; procedure solve(var x,y:number;a,b:number); beginx:=a*cosa+b*sina; y:=b*cosa-a*sina;

13、end;procedure check(y1,x1,y2,x2:long);var i,c:longbegin;if ififx1=n then exit; y1=n then exit;sty1,x1+n+1=. then exit;p11.x:=x1; p11.y:=y1;p12.x:=x1+1; p12.y:=y1;p13.x:=x1+1; p13.y:=y1+1;p14.x:=x1; p14.y:=y1+1;p21.x:=x2; p21.y:=y2;p22.x:=x2+1; p22.y:=y2;p23.x:=x2+1; p23.y:=y2+1;p24.x:=x2; p24.y:=y2+

14、1;solve(p21.x,p21.y,p21.x,p21.y);solve(p22.x,p22.y,p22.x,p22.y);solve(p23.x,p23.y,p23.x,p23.y);solve(p24.x,p24.y,p24.x,p24.y);c:=er_CP(p1,p2,4,4,p0);ch:=sty1,x1+n+1; ansch:=ansch+area(p0,c); end;begin/ assign(input,input.txt); reset(input); readln(n,alfa); alfa:=alfa/180*pi; sina:=sin(alfa); cosa:=c

15、os(alfa);for i:=n-1 downto -n do readln(sti); if alfazero then beginfor i:=1 to n do beginfor j:=1 end;for i:=n-1for j:=1to n*4 do write(.); wrin;downto -n do beginto n do write(.);write(sti);for j:=1 to n do write(.);wriend;n;for i:=1 to n do beginfor j:=1 to n*4 do write(.); wri end;halt;end;n;if

16、pi/2-alfazero then dec(jj); ii:=trunc(y); if ii-yzero then dec(ii); fillchar(ans,sizeof(ans),0);for k:=1 to 9 do check(ii+dyk,jj+dxk,i,j); flag:=false;for ch:=a to z doif ansch-0.5zero then begin flag:=true; break if flag then write(ch) else write(.);end;end;wri end;end.n;原题描述：1616. Square Country 4

17、Time Limit: 1.0 second Memory Limit: 64 MBThere had never been trams in Square Country. No doubt, this worriedcitizens a lot. At a referendum, people decidedram network shouldbe built all over the country. They also wanted this network to be connected with the tram network of adjacent Rectangular Co

18、untry. However,when projecting works started, it turned outt there was a problem:Square Country and Rectangular Country had different coordinate systems; moreover, their coordinate axes were not parallel.of Square Country held a meeting with Square Parliament and tooka historic decito turn the coord

19、inate system of the country by anangle about the po(0, 0). The deciturned out to be rathery-owned plots of land were coordinate axes and withunpopular because in Square Country all priva sets of squares with sides parallel to theeger-coordinate verti.t meantt after the historic turn itwould be nesar

20、y to alter the boundaries of private eses. The rulesof establishing new boundaries was approved bys decree. Foreach cell of unit size, a new owner was to be established as follows. Ifthere was a citizen who owned moren a half oft cell, then thiswas to cell was toe the new owner of the whole cell. Ot

21、herwise, the wholee se property.Squareernment asked you to automatize the redistribution of privateproperty. You are given a map where all plots are shown. You must compile a new map in which plots after the turn will be shown.InputPlots located far from the center are not in demand in Square country;t is why all private eses are situated inside the square n, n n, n. The map is a square table in each cell of which there is a lowercase English letter, which is a unique code of the owner of the corresponding plot. If there is a dot in a ce