Diferențe pentru problema/extraterestri între reviziile #2 si #13

extraterestri

Extraterestri (clasa a 8-a)

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

O invazie de $N$ farfurii zburătoare (denumite uzual OZN) dă bătăi de cap autorităților. În fiecare astfel de OZN se află extratereștri care au ca misiune distrugerea planetei noastre. Radarul care a detectat invazia are un ecran similar cu planul [$XOY$]. Fiecare OZN este reprezentat pe ecran printr-un segment de dreaptă.
Pentru anihilarea OZN-urilor, autoritățile dispun de $K$ arme laser. Armele sunt poziționate pe sol (ilustrat pe ecranul radarului prin axa [$OX$]). Fiecare armă emite o rază laser, ilustrată pe ecran printr-o paralelă cu axa [$OY$]. Dacă o rază laser intersectează segmentul de pe ecranul radarului corespunzător unui OZN, raza va omorî toți extratereștrii aflați în OZN-ul respectiv.

O invazie de *N* farfurii zburătoare (denumite uzual OZN) dă bătăi de cap autorităților. În fiecare astfel de OZN se află extratereștri care au ca misiune distrugerea planetei noastre. Radarul care a detectat invazia are un ecran similar cu planul [$XOY$]. Fiecare OZN este reprezentat pe ecran printr-un segment de dreaptă.
 
Pentru anihilarea OZN-urilor, autoritățile dispun de *K* arme laser. Armele sunt poziționate pe sol (ilustrat pe ecranul radarului prin axa [$OX$]). Fiecare armă emite o rază laser, ilustrată pe ecran printr-o paralelă cu axa [$OY$]. Dacă o rază laser intersectează segmentul de pe ecranul radarului corespunzător unui OZN, raza va omorî toți extratereștrii aflați în OZN-ul respectiv.
 

Din păcate, în preajmă se află doar un militar specializat în arme laser, așa că autoritățile doresc să știe exact ce armă trebuie să folosească acesta pentru a distruge cât mai mulți extratereștri.
h2. Cerință

h2. Date de intrare

Fișierul de intrare $extraterestri.in$ conține pe prima linie două numere naturale separate prin spațiu $N$ $K$ reprezentând numărul de OZN-uri și respectiv numărul de arme laser. Pe următoarele $N$ linii sunt descrise cele $N$ OZN-uri, câte unul pe linie. Un OZN este descris prin $5$ numere naturale separate prin câte un spațiu $x1$ $y1$ $x2$ $y2$ [$nr$], reprezentând în ordine coordonatele capetelor segmentului corespunzător $(x1, y1)$, $(x2, y2)$, iar $nr$ – numărul de extratereștri din el. Pe ultima linie se găsesc $K$ numere naturale $a1 a2 a3 ... aK$, separate prin câte un spațiu, reprezentând coordonatele pe axa $OX$ (abscisele) unde sunt amplasate armele laser.

Fișierul de intrare $extraterestri.in$ conține pe prima linie două numere naturale separate prin spațiu *N* *K* reprezentând numărul de OZN-uri și respectiv numărul de arme laser. Pe următoarele *N* linii sunt descrise cele *N* OZN-uri, câte unul pe linie. Un OZN este descris prin $5$ numere naturale separate prin câte un spațiu *x1* *y1* *x2* *y2* *nr*, reprezentând în ordine coordonatele capetelor segmentului corespunzător $([*x1*], [*y1*])$, $([*x2*], [*y2*])$, iar *nr* – numărul de extratereștri din el. Pe ultima linie se găsesc *K* numere naturale *a1 a2 a3 ... aK*, separate prin câte un spațiu, reprezentând coordonatele pe axa $OX$ (abscisele) unde sunt amplasate armele laser.

h2. Date de ieșire

Fișierul de ieșire $extraterestri.out$ va conține $K$ linii. Pe linia $i$ va fi scris numărul total de extratereștri care pot fi distruși cu arma [$i$], considerând armele numerotate în ordinea în care acestea apar în fișierul de intrare.

Fișierul de ieșire $extraterestri.out$ va conține *K* linii. Pe linia *i* va fi scris numărul total de extratereștri care pot fi distruși cu arma *i*, considerând armele numerotate în ordinea în care acestea apar în fișierul de intrare.

h2. Restricții

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

* 1 ≤ *N* ≤ 20 000
* 1 ≤ *K* ≤ 20 000
* 1 ≤ orice coordonată din fișierul de intrare ≤ 2 000 000
* 1 ≤ *nr* ≤ 100, pentru orice OZN
* *x1* < *x2*, pentru orice OZN
* Pe ecranul radarului segmentele ce descriu navele se pot intersecta.
* Dacă raza laser trece prin unul dintre capetele unui OZN atunci acesta este distrus.
* Pentru $50%$ dintre testele de intrare 1 ≤ [*N*]*[*K*] ≤ 10 000 000

h2. Exemplu

table(example).
|_. extraterestri.in |_. extraterestri.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
 
h3. Explicație
 
...

table(example).
|_. extraterestri.in |_. extraterestri.out |_. Explicații |
| 5 3
1 1 3 2 2
2 3 4 1 3
6 5 8 5 8
5 1 7 1 6
6 2 7 4 1
3 7 5
| 5
15
6
| !problema/extraterestri?extraterestri.jpg!
 
Arma care emite din punctul $(3,0)$ doboară farfuriile reprezentate de segmentele
(1,1)(3,2) și (2,3)(4,1) distrugând în total 5 extratereștri.
Arma care emite din punctul $(7,0)$ doboară farfuriile reprezentate de segmentele
(5,1)(7,1), (6,2)(7,4) și (6,5)(8,5) distrugând în total 15 extratereștri.
Arma care emite din punctul $(5,0)$ doboară farfuria reprezentată de segmentul
(5,1)(7,1) și distruge 6 extratereștri.
|

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