program robot; const MAX=100; {maximální počet zadaných bodů} pi=3.1415926535; {pi} chyba=1e-8; {nepřesnost operací s typem real} var n:word; n0:word; {počet zadaných bodů} mx,my:real; {souřadnice bodu M} x,y:array[1..MAX] of real; {souřadnice "zadaných" bodů} setridx,setridy:array[0..MAX+1] of word; {body setříděné dle souřadnic} navstivil:word; {počet bodů, které robot navštívil} body:array[1..MAX] of record setrx,setry:word; {pořadí podle x/y-ové souřadnice} nasl:word; {další bod, který robot navštíví} navst:boolean; {byl tu už robot?} end; i,j:word; {pomocné proměnné} procedure qsortx(p,q:word); {quicksort dle x-ové souřadnice} var i,j,k:word; pivot:real; begin i:=p; j:=q; pivot:=x[setridx[(p+q) div 2]]; repeat while x[setridx[i]]j; if pj; if p0 then uhel:=arctan(y[p]/x[p]) else uhel:=arctan(y[p]/x[p])+pi; {spočteme úhel, o který budeme otáčet} for k:=1 to n do {A otočíme body} begin xnov:=x[k]*cos(uhel)-y[k]*sin(uhel); ynov:=y[k]*cos(uhel)+x[k]*sin(uhel); x[k]:=xnov; y[k]:=ynov end; for k:=1 to n do {Nainicializujeme pole} begin body[k].setrx:=k; body[k].setry:=k; setridx[k]:=k; setridy[k]:=k; end; qsortx(1,n); {Setřídíme dle x-ové souřadnice} qsorty(1,n); {Setřídíme dle y-ové souřadnice} end; function soused(p:word):word; begin if (p and 1)=1 then soused:=p+1 else soused:=p-1 end; function nesoused(p:word):word; begin if (p and 1)=1 then nesoused:=p-1 else nesoused:=p+1 end; {Vytvoříme plán průchodu robota, přičemž právě vycházíme z p-tého bodu, je-li q true vodorovně, je-li false svisle} procedure vytvorplan(p:word;q:boolean); var dalsi,okoli:word; begin body[p].navst:=true; inc(navstivil); if q then {další bod ve stejném řádku/sloupci} dalsi:=setridx[soused(body[p].setrx)] else dalsi:=setridy[soused(body[p].setry)]; body[p].nasl:=dalsi; if not(body[dalsi].navst) then {dokud nejsi na začátku prodlužuj plán} vytvorplan(dalsi,not(q)); if (p>n0) and q then exit; {jsme na konci} if q then {zdalipak je tu ještě nenavštivený bod?} okoli:=setridx[nesoused(body[dalsi].setrx)] else okoli:=setridy[nesoused(body[dalsi].setry)]; if (okoli>=1) and (okoli<=n) and (q or (abs(y[okoli]-y[p])=1) and (okoli<=n) and (q or (abs(y[okoli]-y[p])chyba then exit; for i:=1 to n div 2 do if abs(y[setridy[2*i]]-y[setridy[2*i-1]])>chyba then exit; zparovano:=true end; function vzdal(p,q:word):real; {vzdálenost p-tého a q-tého bodu} begin vzdal:=sqrt(sqr(x[p]-x[q])+sqr(y[p]-y[q])) end; {vektorový součin vektoru z p-tého do q-tého a z q-tého do r-tého bodu} function vektsoucin(p,q,r:word):real; begin vektsoucin:=(x[q]-x[p])*(y[r]-y[q])-(x[r]-x[q])*(y[q]-y[p]) end; begin readln(n0); {načtení vstupu} readln(mx,my); for i:=1 to n0 do begin readln(x[i],y[i]); x[i]:=x[i]-mx; {bod M posuneme do počátku} y[i]:=y[i]-my; end; n:=n0+1; {z bodu M vytvoříme "zadaný" bod} x[n]:=0; y[n]:=0; if (n mod 2=1) then begin inc(n); x[n]:=0; y[n]:=0; end; setridx[0]:=0; setridy[0]:=0; {nastavíme zarážky} setridx[n+1]:=0; setridy[n+1]:=0; for i:=1 to n0 do begin natoc(i); {natočíme si body} for j:=1 to n do body[j].navst:=false; navstivil:=0; if zparovano then {v řádcích a sloupcích je sudý počet bodů} begin if n-n0=2 then {dva přidané body umístíme vedle sebe} begin setridx[body[n0+2].setrx]:=setridx[soused(body[n0+1].setrx)]; body[setridx[soused(body[n0+1].setrx)]].setrx:=body[n0+2].setrx; setridx[soused(body[n0+1].setrx)]:=n0+2; body[n0+2].setrx:=soused(body[n0+1].setrx); setridy[body[n0+2].setry]:=setridy[soused(body[n0+1].setry)]; body[setridy[soused(body[n0+1].setry)]].setry:=body[n0+2].setry; setridy[soused(body[n0+1].setry)]:=n0+2; body[n0+2].setry:=soused(body[n0+1].setry); end; vytvorplan(n0+1,false) end; if navstivil=n then {prošli jsme všemi body?} begin j:=n0+1; {začneme v bodě M} writeln('Robot je natočen k ',body[j].nasl,'-tému bodu.'); writeln('Program pro robota:'); write('G(',vzdal(j,body[j].nasl):0:2,')'); while(body[j].nasl<=n0) do {a skončíme v bodě M} begin if vektsoucin(j,body[j].nasl,body[body[j].nasl].nasl)<0 then write(',R') else write(',L'); j:=body[j].nasl; write(',G(',vzdal(j,body[j].nasl):0:2,')'); end; writeln; {odřádkujeme a skončíme} exit end end; writeln('Program pro robota nelze sestavit.'); end.