== include(page="template/taskheader" task_id="volei") ==
La ora de sport elevii doresc să joace volei. Sunt exact $N$ fete şi $N$ băieţi şi se doreşte formarea a două echipe, o echipă formată numai din fete, iar cealaltă numai din băieţi. Iniţial, elevii au o poziţie fixată pe teren. Ei pot fi reprezentaţi ca $2N$ puncte de coordonate întregi în plan. Pentru a putea începe jocul, profesorul de sport trebuie să traseze un fileu (o dreaptă) între echipa băieţilor şi echipa fetelor, astfel încât cele două echipe să se afle de o parte şi de alta a fileului. Cum trasarea unui fileu între cele două echipe poate să nu fie posibilă conform aşezării iniţiale, trebuie să fie efectuate unele schimbări. Astfel, profesorul poate alege la un moment dat o singură fată şi un singur băiat, situaţi la distanţa maxim $D$ şi să le interschimbe poziţiile (fata va trece în locul băiatului, iar băiatul în locul fetei).
h2. Cerinta
Să se determine numărul minim de mutări pe care trebuie să le efectueze profesorul de sport pentru a fi posibilă amplasarea unui fileu, precum şi mutările efectuate.
Poveste şi cerinţă...
h2. Date de intrare
Fişierul de intrare $volei.in$ conţine pe prima linie $N$, numărul de fete, egal cu numărul de băieţi. A doua linie va conţine numărul natural nenul $D$, cu semnificaţia din enunţ. Fiecare dintre următoarele $2N$ linii va conţine un triplet de forma $x$ $y$ $tip$, unde $x$ $y$ sunt coordonatele iniţiale ale unui elev (abscisa, ordonata), iar tip este caracterul $B$ dacă elevul corespunzător este băiat sau $F$ dacă este fată.
Fişierul de intrare $volei.in$ ...
h2. Date de ieşire
Fişierul de ieşire volei.out va conţine pe prima linie un număr natural nrmin reprezentând numărul minim de mutări care trebuie să fie efectuate. Pe următoarele nrmin linii se vor afişa mutările efectuate, câte o mutare pe o linie, în ordinea efectuării lor. O mutare este descrisă sub forma $x{~1~}$ $y{~1~}$ $x{~2~}$ $y{~2~}$, cu semnificaţia că elevii situaţi la poziţiile ({$x{~1~}$}, $y{~1~}$) şi ({$x{~2~}$}, $y{~2~}$) vor fi interschimbaţi.
În fişierul de ieşire $volei.out$ ...
h2. Restricţii
* $2$ ≤ $N$ ≤ $7$
* $1$ ≤ $D$ ≤ $30000$
* Coordonatele sunt numere întregi din intervalul [-{$10000$}, $10000$]
* Nu vor exista $3$ poziţii coliniare.
* Nu vor exista două persoane în aceeaşi poziţie.
* Distanţa dintre punctele ({$x{~1~}$}, {$y{~1~}$}) şi ({$x{~2~}$}, {$y{~2~}$}) este sqrt(({$x{~1~}$} - {$x{~2~}$})^2^ + ({$y{~1~}$} - {$y{~2~}$})^2^).
* Dacă sunt mai multe soluţii posibile, afişaţi oricare dintre acestea.
* Se va acorda $40$% din punctajul pe test dacă numărul de mutări este corect, respectiv $100$% din punctaj dacă atât numărul mutărilor, cât şi mutarile efectuate sunt corecte.
* Pentru $50$% dintre teste $D$ mai mare decât maximul distanţelor între oricare două puncte.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. volei.in |_. volei.out |
|3
4
-2 4 B
-1 3 F
-1 -2 B
1 5 F
3 3 F
6 6 B
|2
-2 4 -1 3
-1 3 3 3
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
!problema/volei?fete.jpg!
Se interschimbă băiatul de la poziţia (-{$2$},{$4$}) cu fata de la poziţia (-{$1$},{$3$}). Apoi se interschimbă băiatul de la poziţia (-{$1$},{$3$}) cu fata de la poziţia ({$3$},{$3$}).
...
== include(page="template/taskfooter" task_id="volei") ==
