2558 - Shootings

De când a început serviciul militar, Mihai nu și-a găsit vocația și a decis să-și încerce norocul încă o dată, mergând la superiorul său, Căpitanul Dan. De data aceasta, Dan a fost mai amabil, dar i-a cerut lui Mihai să demonstreze talentul său de trăgător.

Vom considera țintele din zona de tragere ca fiind dreptunghiuri în plan. Căpitanul îi indică lui Mihai câteva puncta pe axa OX și direcțiile de tragere. Fiecare tragere este o semidreaptă care poate fi orientată fie diagonal spre stânga la 45o, fie diagonal spre dreapta la 45o, fie pe verticală în sus.

Definim costul atingerii unei ținte ca fiind lungimea intersecției semidreptei de tragere cu dreptunghiul care reprezintă ținta. Dacă intersecția este vidă, sau constă dintr-un singur punct, atunci costul este 0. Definim costul unei trageri ca suma costurilor atingerilor tuturor țintelor.

Cerința

Determinați costul fiecărei trageri.

Date de intrare

Fișierul de intrare shootings.in conține pe prima linie numărul natural N, reprezentând numărul de dreptunghiuri-ținte. Fiecare din următoarele N linii, conține descrierea unui dreptunghi–țintă: patru numere naturale, X1, Y1, X2, Y2, care reprezintă coordonatele colțului din stânga-jos și dreapta-sus, respectiv. Cele partu numere sunt separate prin câte un spațiu. Urmează o linie care conține numărul natural T, reprezentând numărul de împușcături. Fiecare din următoarele T linii, conține două numere întregi P și D, separate prin spațiu. Primul număr reprezintă coordonata X a punctului de tragere, cel de al doilea – direcția de tragere (D = 1 corespunde unei trageri verticale, D = 2 corespunde unei trageri diagonale spre stânga și D = 3 corespunde unei trageri diagonale spre dreapta).

Date de ieșire

Fișierul de ieșire shootings.out are T linii. Fiecare linie conține un număr întreg non-negativ, care reprezintă pătratul costului unei trageri. Pătratele costurilor apar în fișierul de ieșire în aceeași ordine în care tragerile apar în fișierul de intrare. Reamintim că pentru fiecare din costurile determinate, se va scrie pătratul valorii sale.

Restricții și precizări

• 1 ≤ N ≤ 50000
• 1 ≤ T ≤ 100000
• 1 ≤ X1 < X2 ≤ 100000, 1 ≤ Y1 < Y2 ≤ 100000
• -100000 ≤ P ≤ 200000
• toate laturile dreptunghiurilor sunt paralele axei OX sau OY
• oricare două dreptunghiuri nu se intersectează (nu au nici un punct comun) și nu există dreptunghiuri incluse unul în celălalt.
• dreptunghiurile pot fi pătrate
• dreptunghiurile au arie diferită de 0
• pot exista trageri identice
• de remarcat că numerele din fișierul de ieșire sunt întregi, non-negative

Exemplu:

shootings.in

4
1 1 4 3
2 4 5 7
6 3 10 5
8 1 9 2
2
0 3
9 1

shootings.out

18
9

def calculate_intersection_length(rect, ray_origin, direction):
    x1, y1, x2, y2 = rect
    x0, y0 = ray_origin

    if direction == "left":
        # Equation of the line: y = -(x - x0) + y0 (negative slope)
        intersections = []
        # Check intersection with left side of the rectangle
        y = -(x1 - x0) + y0
        if y1 <= y <= y2:
            intersections.append((x1, y))
        # Check intersection with bottom side of the rectangle
        x = -(y1 - y0) + x0
        if x1 <= x <= x2:
            intersections.append((x, y1))
        # Check intersection with top side of the rectangle
        x = -(y2 - y0) + x0
        if x1 <= x <= x2:
            intersections.append((x, y2))

    elif direction == "right":
        # Equation of the line: y = (x - x0) + y0 (positive slope)
        intersections = []
        # Check intersection with right side of the rectangle
        y = (x2 - x0) + y0
        if y1 <= y <= y2:
            intersections.append((x2, y))
        # Check intersection with bottom side of the rectangle
        x = (y1 - y0) + x0
        if x1 <= x <= x2:
            intersections.append((x, y1))
        # Check intersection with top side of the rectangle
        x = (y2 - y0) + x0
        if x1 <= x <= x2:
            intersections.append((x, y2))

    elif direction == "up":
        # Vertical line upwards
        intersections = []
        # Check intersection with top side of the rectangle
        if x1 <= x0 <= x2:
            intersections.append((x0, y2))
        # Check intersection with bottom side of the rectangle
        if x1 <= x0 <= x2:
            intersections.append((x0, y1))

    # Calculate length of intersection segment
    if len(intersections) == 2:
        (xA, yA), (xB, yB) = intersections
        return ((xB - xA)**2 + (yB - yA)**2)**0.5
    else:
        return 0

def calculate_shooting_cost(rectangles, shots):
    costs = []
    for shot in shots:
        origin, direction = shot
        total_cost = 0
        for rect in rectangles:
            total_cost += calculate_intersection_length(rect, origin, direction)
        costs.append(total_cost)
    return costs

# Exemplu de utilizare
rectangles = [
    (1, 1, 4, 4),  # dreptunghi definit prin (x1, y1, x2, y2)
    (5, 3, 7, 5)
]

shots = [
    ((2, 0), "left"),   # tragere de la (2, 0) în direcția diagonală stânga
    ((6, 0), "right"),  # tragere de la (6, 0) în direcția diagonală dreapta
    ((3, 0), "up")      # tragere de la (3, 0) în direcția verticală în sus
]

costs = calculate_shooting_cost(rectangles, shots)
for i, cost in enumerate(costs):
    print(f"Costul tragerii {i+1}: {cost}")