2478 - Laser

Enunt

Considerăm N 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) care este originea sistemul de axe ortogonale XOY, se află un laser care poate transmite câte un fascicul de lumină în orice punct cu ordonata pozitivă (≥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ţa

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 N de segmente. Pe următoarele N linii se află câte cinci numere întregi x1 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 dacă nu există soluție.

Restricţii şi precizări

• 1 ≤ N ≤ 5000
• -109 ≤ abscisele punctelor ≤ 109
• 0 ≤ ordonatele punctelor ≤ 109
• 0 ≤ costurile segmentelor ≤ 109
• Se garantează că punctul O(0,0) nu se află pe niciunul din cele N segmente
• La evaluare se vor folosi fișiere de intrare în valoare de 30 de puncte care au pentru toate segmentele costul egal cu 1

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)] și [(2, 3), (5,0)]. Segmentele [(-5, 0), (-2,4)] și [(-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)].

Rezolvare

<syntaxhighlight lang="python" line> import math

def calculate_angle(x1, y1, x2, y2):

   dx = x2 - x1
   dy = y2 - y1
   return math.atan2(dy, dx)

def sort_segments(segments):

   return sorted(segments, key=lambda seg: calculate_angle(seg[0], seg[1], seg[2], seg[3]))

def min_obstruction_cost(segments):

   segments.sort(key=lambda x: x[4])  
   segments = sort_segments(segments)  

   total_cost = 0
   max_y = 0
   for seg in segments:
       if seg[1] > max_y:
           total_cost += seg[4]
           max_y = seg[1]

   return total_cost if max_y > 0 else -1

with open("laser.in", "r") as fin:

   N = int(fin.readline().strip())
   segments = [list(map(int, fin.readline().split())) for _ in range(N)]

result = min_obstruction_cost(segments)

with open("laser.out", "w") as fout:

   fout.write(str(result))

</syntaxhighlight>