Fişierul intrare/ieşire:menger.in, menger.outSursăACM 2014
AutorVlad ManeaAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.25 secLimită de memorie4608 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Menger

Avem un cub fractal aşezat cu un colţ în originea sistemului de coordonate, şi cu toate celelalte colţuri la coordonate pozitive sau zero.
Cubul se construieşte astfel:

  • Cubul de grad 0 este cubul unitate
  • Cubul de grad n+1 este mulţimea (x, y, z) din R3 cu proprietatea că există i, j, k din {0, 1, 2} astfel încât (3x-i, 3y-j, 3z-k) face parte din cubul de grad n, şi cel puţin unul dintre i, j, k este 1.

Cuburile de grade 0, 1, 2, 3 sunt ilustrate la scară în imaginea de mai jos.

Vrem să calculăm volumul intersecţiei unui astfel de cub cu un paralelipiped dreptunghic, având muchiile paralele cu axele sistemului de coordonate, ale cărui colţuri sunt cunoscute.

Date de intrare

Fişierul de intrare menger.in conţine pe prima linie numărul de teste T. Fiecare test conţine două linii. Pe prima linie se găseşte gradul G al cubului. Pe următoarea linie se găsesc 6 numere, care reprezintă coordonatele punctelor ce definesc o diagonală a paralelipipedului dreptunghic: (X1, Y1, Z1) şi (X2, Y2, Z2), în această ordine.

Date de ieşire

În fişierul de ieşire menger.out se găsesc T linii. Pe fiecare linie se găseşte în ordine volumul intersecţiei celor două corpuri geometrice.

Restricţii

  • T = 20
  • 0 ≤ G ≤ 5
  • 0 ≤ X1 ≤ X2 ≤ 103
  • 0 ≤ Y1 ≤ Y2 ≤ 103
  • 0 ≤ Z1 ≤ Z2 ≤ 103

Exemplu

menger.inmenger.out
1
0
0 0 0 2 3 4
1

Explicaţie

Fişierul de intrare conţine 1 test.
Cubul de grad 0 are volumul 1 şi ocupă spaţiul dintre (0, 0, 0) şi (1, 1, 1).
O parte din paralelipiped ocupă acelaşi spaţiu dintre (0, 0, 0) şi (1, 1, 1), de volum 1.
Fişierul de ieşire conţine 1 linie cu acest volum.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content