Simulare ONI 2018 | laser

This was the problem page during the contest. Access the current page here.
Time limit: 0.2s Memory limit: 64MB Input: laser.in Output: laser.out

Considerăm NN segmente în plan identificate prin coordonatele extremităților lor. Toate segmentele sunt închise, adică fiecare conține și cele două puncte considerate extremitățile sale. Presupunem că în punctul O(0,0)O(0,0) care este originea sistemul de axe ortogonale XOYXOY, se află un laser care poate transmite câte un fascicul de lumină în orice punct cu ordonata pozitivă (0)(\geq 0). Fasciculul poate fi reprezentat în plan, ca o semidreaptă cu extremitatea în originea axelor. Totuși, dacă fasciculul de lumină întâlnește un segment, acesta îl obturează, adică îl împiedică să treacă mai departe de acesta. Considerăm că fiecare segment are asociat un număr care reprezintă un cost pentru desenarea lui în plan.

Cerință

Determinaţi costul total minim al segmentelor care pot fi alese pentru a obtura orice fascicul de lumină care ar pleca din origine către un punct cu ordonata pozitivă.

Date de intrare

Fișierul de intrare laser.in conține pe prima linie numărul natural NN de segmente. Pe următoarele NN linii se află câte cinci numere întregi x1,y1,x2,y2x1, y1, x2, y2 cost, separate prin câte un spațiu. Primele patru numere reprezintă coordonatele extremităților fiecărui segment, pentru fiecare dintre ele în ordine abscisa și ordonata, iar ultimul număr de pe linie reprezintă costul segmentului.

Date de ieșire

Fișierul de ieșire laser.out va conține un număr reprezentând costul minim determinat sau 1-1 dacă nu există soluție.

Restricții și precizări

  • 1N5 0001 \leq N \leq 5 \ 000
  • 109-10^9 \leq abscisele punctelor 109\leq 10^9
  • 00 \leq ordonatele punctelor 109\leq 10^9
  • 00 \leq costurile segmentelor 109\leq 10^9
  • Se garantează că punctul O(0,0)O(0,0) nu se află pe niciunul din cele NN segmente
  • La evaluare se vor folosi fișiere de intrare în valoare de 3030 de puncte care au pentru toate segmentele costul egal cu 11

Exemplul 1

laser.in

4
2 3 5 0 2
2 3 -4 4 1
-2 4 -5 0 1
6 0 -14 1 8

laser.out

4

Explicație

S-au ales segmentele de cost total minim [(5,0),(2,4)],[(4,4),(2,3)][(-5, 0), (-2,4)], [(-4, 4), (2,3)] și [(2,3),(5,0)][(2, 3), (5,0)]. Segmentele [(5,0),(2,4)][(-5, 0), (-2,4)] și [(14,1),(6,0)][(-14, 1), (6,0)] obturează orice fascicul dar are cost total mai mare

Exemplul 2

laser.in

4
-1 3 1 3 1
-2 0 -1 1 1
2 0 1 1 1
1 1 -1 1 1

laser.out

3

Explicație

S-au ales segmentele: [(2,0),(1,1)],[(1,1),(1,1)],[(1,1),(2,0)][(-2, 0), (-1,1)], [(-1, 1), (1,1)], [(1, 1), (2,0)].

Exemplul 3

laser.in

3
-1 3 1 3 1
-2 0 -1 1 4
2 0 1 1 5

laser.out

-1

Explicație

Nu există segmente care să respecte cerințele.

Log in or sign up to be able to send submissions!