.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » sea

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
sea


Timp maxim de execuţie / test:
0.5s
Memorie totala disponibilă / stivă:
16MB / 1MB

Pe mare se află N vapoare. Malul este în mod curios perfect drept şi este reprezentat prin axa Ox a sistemului de coordonate. Cele N vapoare sunt reprezentate prin perechi de coordonate (Vxi, Vyi), unde Vyi este strict pozitiv (marea este deasupra axei Ox). Pe mal se află M faruri, date prin coordonatele lor Fxi (fiind exact la limita dintre mare şi uscat, y-ul lor este întotdeauna 0). Cele M faruri sunt ciudate pentru că ele nu pot lumina decât în stânga. Astfel aria luminată de fiecare far i este delimitată de un sfert de cerc cu o rază Fri. Mai exact, un vapor este luminat de un anumit far dacă se află în stânga farului (are x-ul mai mic) şi distanţa de la far la vapor este mai mică sau egală cu valoarea Fri asociată farului respectiv.
Pentru fiecare far se mai dă şi un număr natural strict pozitiv Fni. Din motive greu de înţeles, şeful portului doreşte ca fiecare far i să lumineze cel puţin Fni vapoare (un vapor poate fi luminat de mai multe faruri). El doreşte consum minim de energie şi vrea să afle pentru fiecare far raza minimă necesară pentru a lumina numărul cerut de vapoare.

Cerinţă

Determinaţi pentru fiecare far valoarea Fri care reprezintă raza minimă necesară pentru ca farul să lumineze cel puţin Fni vapoare.

Date de intrare

Prima linie a fişierului sea.in conţine două numere întregi N şi M separate printr-un spaţiu, reprezentând numărul de vapoare, respectiv numărul de faruri. Fiecare dintre următoarele N linii conţine câte o pereche de numere reale separate printr-un spaţiu Vxi şi Vyi (coordonatele vapoarelor). Fiecare dintre următoarele M linii conţine câte o pereche de numere separate printr-un spaţiu, unul real Fxi şi unul întreg Fni (coordonatele orizontale şi numerele asociate farurilor).

Date de ieşire

Fişierul sea.out va conţine M linii, fiecare linie conţinând un număr real, dat cu 4 zecimale: pe linia i se află raza minimă necesară pentru ca farul i să lumineze Fni vapoare.

Restricţii

• 1 <= N <= 400
• 1 <= M <= 100 000
• 0 < y, r < 100 000, -100 000 < x < 100 000, 1 <= Fni <= N

• În fişierul de intrare farurile sunt sortate crescător după coordonatele x.
• Nu vor exista două vapoare, sau un far şi un vapor cu acelaşi x. În schimb pot exista două sau mai multe faruri cu acelaşi x, caz în care ele vor fi unul lângă altul în fişierul de intrare (evident din moment ce sunt sortate după x). Ordinea în care apar în fişierul de intrare farurile cu acelaşi x nu este definită. Pot exista chiar două faruri identice.
• Numerele reale din fişierul de intrare vor avea maxim 4 zecimale
• Rezultatul va fi verificat cu o precizie de 0.001 (rezultatul va fi considerat corect dacă modulul diferenţei dintre rezultatul corect şi cel furnizat de concurent nu depăşeşte 0.001)
• Există întotdeauna soluţie (pentru fiecare far i vor exista întotdeauna cel puţin Fni vapoare în stânga lui).

Exemple

sea.insea.out
3 5 -0.5 0.5 -2 5 3 4 -1 1 0 1 0 2 0 1 5 1 5.0990 0.7071 5.3852 0.7071 4.4721

autor: Radu Berinde
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor