Inverseaza reviziile

Diferente pentru problema/hvrays intre reviziile #1 si #6

Diferente intre titluri:

hvrays

Hvrays

Diferente intre continut:

== include(page="template/taskheader" task_id="hvrays") ==

Poveste si cerinta...

Se dau $H$ raze orizontale si $V$ raze verticale. O raza orizontala este o linie dreapta care are originea intr-un punct si se extinde la infinit spre dreapta (spre coordonate $X$ crescatoare). O raza verticala este o linie dreapta ce are originea intr-un punct si se extinde la infinit in jos (catre coordonate $Y$ descrescatoare). O raza orizontala a carei origine este $(X{~h~},Y{~h~})$ atinge o raza verticala a carei origine este $(X{~v~},Y{~v~})$ daca $X{~h~} ≤ X{~v~}$ si $Y{~h~} ≤ Y{~v~}$.
 
Determinati o submultime $S$ constand dintr-un numar minim de raze verticale astfel incat fiecare raza orizontala sa fie atinsa de cel putin o raza verticala din $S$. Se garanteaza ca pe testele folosite va exista o astfel de submultime.

h2. Date de intrare

...

Prima linie a fisierului de intrare $hvrays.in$ contine un numar intreg $T$, reprezentand numarul de teste ce urmeaza. Prima linie a fiecarui test contine $2$ numere intregi: $H$ si $V$. Urmatoarele $H$ linii contin cate $2$ numere intregi: $X$ si $Y$, reprezentand coordonatele $(X,Y)$ ale originilor razelor orizontale. Urmatoarele $V$ linii contin cate $2$ numere intregi: $X$ si $Y$, reprezentand coordonatele $(X,Y)$ ale originilor razelor verticale.

h2. Date de iesire

...

Pentru fiecare din cele $T$ teste date, in ordinea din fisierul de intrare, afisati in fisierul de iesire $hvrays.out$ o linie continand numarul minim de raze verticale ale submultimii $S$.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ T ≤ 12$
* $1 ≤ H ≤ 100 000$
* $1 ≤ V ≤ 100 000$
* Coordonatele originilor tuturor razelor sunt numere intregi din intervalul $[0,50 000 000]$.

h2. Exemplu
table(example). |_. hvrays.in |_. hvrays.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

|1
3 3
1 6
4 4
6 2
3 8
5 7
9 4
|2|

h3. Explicatie

...

Solutia poate consta din a doua si a treia raza verticala. O alta solutie poate fi formata din prima si a treia raza verticala.
!problema/hvrays?hvrays.jpg!

== include(page="template/taskfooter" task_id="hvrays") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 

2182