Fişierul intrare/ieşire:sea.in, sea.outSursăbaraj 2004
AutorRadu BerindeAdăugată demarius135Dumitran Adrian Marius marius135
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sea

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.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
  • Numerele trebuie afisare in output cu o precizie de EXACT 4 decimale.
  • 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).

Exemplu

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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?