Fişierul intrare/ieşire:hvrays.in, hvrays.outSursăSelectie echipe ACM ICPC, UPB 2007
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.55 secLimită de memorie67583 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Hvrays

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 (Xh,Yh) atinge o raza verticala a carei origine este (Xv,Yv) daca Xh ≤ Xv si Yh ≤ Yv.

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.

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.

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.

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].

Exemplu

hvrays.inhvrays.out
1
3 3
1 6
4 4
6 2
3 8
5 7
9 4
2

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content