Bubbles - CPPC

Lui Vasilică îi place foarte mult să facă baloane de săpun. Împreună cu prietena lui, Vasilică, petrece mult timp amestecând diverse tipuri de săpun și obținând tot felul de soluții ingenioase, pentru ca baloanele să fie cât mai frumoase și colorate. Dar, cum orice bucurie durează puțin, aceste baloane la un moment dat se sparg. Cei doi s-au gândit că ar fi interesant să știe când se întâmplă asta. Ca să afle, ei s-au hotărât să simuleze pe calculator ce se întâmplă cu baloanele într-un interval de timp. Dar pentru asta au nevoie de puțin ajutor la programarea unei astfel de simulări.

Cerința problemei

Într-o cameră sunt n baloane de săpun.

Pentru a putea delimita camera într-un reper cartezian, se dau locațiile pe axe ale pereților. Pereții sunt paraleli cu planele de coordonate, astfel că distanțele până la origine se pot măsura pe cele trei axe:

$w_{x_{1}}$

$w_{x_{2}}$

$w_{y_{1}}$

$w_{y_{2}}$

$w_{z_{1}}$

$w_{z_{2}}$

adică cei doi pereți paraleli cu YOZ se află la distanțele w_x1, respectiv w_x2, cei doi pereți paraleli cu XOZ se află la distanțele w_y1, respectiv w_y2 și cei doi pereți paraleli cu XOY se află la distanțele w_z1, respectiv w_z2, față de origine.

Indicii x,y,z reprezintă axele (OX, OY, respectiv OZ) pe care se măsoară distanța față de origine. Nu e obligatoriu ca w_x1 < w_x2, w_y1 < w_y2 și w_z1 < w_z2. În plus, se consideră întotdeauna primele două numere ca fiind distanțele măsurate pe OX, următoarele două pe OY, și ultimele două pe OZ. De exemplu:

1) 400 600 0 700 700 800 este același lucru cu

2) 600 400 0 700 800 700, dar nu este același lucru cu

3) 0 700 700 800 400 600

În primele două cazuri camera va fi aceeași având:

lungimea = |w_x1 – w_x2| = 200 cm

înălțimea = |w_y1 – w_y2| = 700 cm

lățimea = |w_z1 – w_z2| = 100 cm,

în timp ce în cazul al treilea,

lungimea = |w_x1 – w_x2| = 700 cm

înălțimea = |w_y1 – w_y2| = 100 cm

lățimea = |w_z1 – w_z2| = 200 cm

Fiecare balon de săpun este dat prin poziția centrului său (la momentul inițial): x,y,z, prin raza sa, r, și prin viteza (constanta) pe care o are, v , (mai exact componentele vitezei pe cele trei axe: v_x, v_y,v_z). Se consideră că toate distanțele se măsoară în cm, respectiv pentru viteze, cm/s. Când un balon întâlnește un perete, el se sparge. Când se întâlnesc două sau mai multe baloane, toate baloanele implicate în coliziune se sparg.

Cazuri posibile de ciocnire

Se consideră două baloane, având razele r₁, respectiv r₂ și pozițiile la momentul t: (x₁, y₁, z₁), respectiv (x₂, y₂, z₂) . La momentul t+1, pozițiile sunt notate cu (x’₁, y’₁, z’₁), respectiv (x’₂, y’₂, z’₂). Vectorii viteză sunt dați de v₁ = (v_x1,v_y1,v_z1) și v₂ = (v_x2,v_y2,v_z2). Notăm cu d distanța între centrele baloanelor.

Cele două baloane se ciocnesc în momentul t+1, în oricare dintre următoarele cazuri, indiferent dacă este posibil ca, în intervalul (t, t+1), ele să nu fi trecut simultan prin același loc, și nici să se fi atins (orice condiție de mai jos se aproximează drept ciocnire):

La momentul t+1, d <=
$r_{1}$
+
$r_{2}$
.
Baloanele s-au depășit (întâlnit) în intervalul (t, t+1), dar în momentul t+1, d >
$r_{1}$
+
$r_{2}$
. Aici se disting două subcazuri:
1. Traiectoriile baloanelor sunt paralele și distanța dintre traiectorii este <=
$r_{1}$
+
$r_{2}$
.
2. Traiectoriile baloanelor sunt neparalele (inclusiv necoplanare) și distanța dintre traiectorii este <=
$r_{1}$
+
$r_{2}$
.

În orice altă situație, considerăm că baloanele nu se ciocnesc.

Pentru a ști dacă două baloane s-au depășit într-un interval de o secundă, se rețin relațiile dintre pozițiile lor la momentele t și t+1. Dacă există cel puțin o axă pe care relația între coordonate s-a inversat, atunci baloanele s-au depășit. Exemplu:

La momentul t:

x₁ < x₂, y₁ < y₂, z₁ < z₂.

La momentul t+1:

x’₁ > x’₂, y’₁ < y’₂, z’₁ < z’₂.

Notă! – Distanța dintre două drepte din spațiu se măsoară pe dreapta perpendiculară pe cele două drepte.

Se cere să se scrie un program care simulează mișcarea baloanelor în cameră. Simularea se va face începand cu momentul t₀ = 0 până la, cel mult, t_max, dat. Dacă nu mai sunt baloane, simularea se oprește, chiar dacă t_max nu a expirat. Timpul va fi dat în secunde, și se va analiza starea sistemului din secundă în secundă. Se va afișa această stare, de fiecare dată când dispare cel puțin un balon.

Se recomandă următorul algoritm:

verificarea existenței a cel putin un balon în cameră + verificarea dacă la momentul t=0 nu există baloane care se ating între ele sau de pereți
- ieșirea din program, în cazul în care nu există baloane în cameră, sau pornirea simulării cu numărul de baloane existente în cameră
cât timp nu a expirat t_max se repetă pașii:
- verificarea ciocnirilor cu pereții, și marcarea baloanelor implicate pentru a fi șterse
- verificarea ciocnirilor a două sau mai multe baloane, și marcarea acestora pentru ștergere (ciocnirile începând cu momentul t=1, implică și verificarea traiectoriilor, ca mai sus)
- ștergerea baloanelor marcate
- afișarea rezultatelor, dacă este cazul (dacă a fost șters cel puțin un balon)
- avansarea pozițiilor (în funcție de viteze) și timpului cu o unitate

Atenție! – Simularea unei secunde NU înseamnă că porțiunea de program corespunzatoare trebuie să se execute într-o secundă! Timpul real de execuție al programului va fi intotdeauna mult mai mic decat t_max. O secundă este simulată printr-o iterație. Instrucțiunile corespunzatoare unei iterații se vor executa în mult mai puțin de o secundă.

Formatul datelor de intrare

Pe prima linie sunt date coordonatele pereților (numere reale), pe a doua linie, timpul maxim de simulare (întreg pozitiv), pe a treia linie, numărul inițial de baloane, n (întreg pozitiv), și pe fiecare dintre următoarele n linii, coordonatele centrului, raza și viteza balonului (numere reale):

$w_{x_{1}}$

$w_{x_{2}}$

$w_{y_{1}}$

$w_{y_{2}}$

$w_{z_{1}}$

$w_{z_{2}}$

$t_{max}$

$x_{1}$

$y_{1}$

$z_{1}$

$r_{1}$

$v_{x_{1}}$

$v_{y_{1}}$

$v_{z_{1}}$

………………………………………

$x_{n}$

$y_{n}$

$z_{n}$

$r_{n}$

$v_{x_{n}}$

$v_{y_{n}}$

$v_{z_{n}}$

Pentru numere reale se va folosi tipul double.

t_max < 0 sau n < 0.

Se considera vitezele nenule. Pentru fiecare viteză, cel puțin o axă va avea valoare nenulă.

În cazul în care coordonatele centrului unui balon nu se află în interiorul camerei, balonul nu va fi luat în considerare la simulare. Simularea se va face pentru cele n’ baloane (n’ = n – nr_baloane_în_afara_camerei – nr_baloane_sparte_la_momentul_0).

Formatul datelor de ieșire

Pe prima linie se va scrie numărul de baloane cu care se începe simularea, n’ . Pentru fiecare moment când dispare cel puțin un balon, se va scrie o secvență de tipul: momentul de timp, număr de baloane rămase,pozițiile baloanelor rămase. În cazul în care nu a expirat t_max, și au dispărut toate baloanele, ultimul moment afișat, trebuie să fie cel în care s-au spart ultimele baloane (t_f). Dacă baloanele se sparg în intervalul (t, t+1], momentul de timp care se afișeaza va fi t+1. Exemplu:

$n^{'}$