3034 - Drept 1

Enunt

Numim poligon drept un poligon cu laturile consecutive perpendiculare și lungimile laturilor numere naturale nenule. Un poligon drept cu n laturi este descris de un șir de n numere întregi nenule în care lungimile laturilor sunt date de valoarea absolută a numerelor din șir, iar semnul precizează poziția laturilor, un număr pozitiv însemnând latură spre dreapta sau în sus față de extremitatea laturii precedente, iar un număr negativ însemnând latură în jos sau spre stânga față de extremitatea laturii precedente; de exemplu șirul 1, 1, -1, -1 reprezintă un pătrat de latură 1 (prima latură spre dreapta, a doua în sus, a treia spre stânga, a patra în jos). Vom considera laturile ca fiind orizontale sau verticale, prima latură enumerată fiind orizontală spre dreapta, dacă numărul este pozitiv, sau spre stânga, dacă numărul este negativ.

Cerinţa

Se dau unul sau mai multe șiruri de numere întregi nenule. 1. Să se stabilească, pentru fiecare dintre ele, dacă reprezintă un poligon drept. 2. Știind că șirurile date reprezintă poligoane drepte, să se determine aria fiecăruia.

Date de intrare

Fișierul de intrare drept.in conține pe prima linie, separate prin spațiu, un număr natural C și un număr natural T. Următoarele 2 * T linii vor descrie testele, câte două linii pentru fiecare test. Pe prima linie corespunzătoare unui test se află un număr natural n, iar pe a doua linie un șir de n numere întregi, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire drept.out va conține pe o singură linie rezultatele corespunzătoare celor T teste, separate prin câte un spațiu. Dacă C = 1 pentru fiecare șir rezultatul este 1, dacă acesta reprezintă un poligon drept, sau 0 altfel. Dacă C = 2 pentru fiecare șir rezultatul este aria poligonului drept corespunzător.

Restricţii şi precizări

• 1 ≤ T ≤ 10
• 4 ≤ n ≤ 100
• Pentru teste în valoare de 45 de puncte C = 1, pentru restul de 55 de puncte C = 2
• Pentru teste în valoare de 30 de puncte C = 1 și numerele ce descriu figura sunt întregi nenule aparținând intervalului [-100, 100]
• Pentru celelalte 15 puncte și C = 1 numerele ce descriu figura sunt întregi nenule aparținând intervalului [-1.000.000.000, 1.000.000.000]
• Pentru teste în valoare de 33 de puncte se garantează că avem C = 2 și intersecția dintre orice orizontală cu poligonul este fie vidă, fie formată dintr-un singur segment.
• Pentru testele în care valoarea lui C este 2, numerele din șirul ce descrie poligonul sunt întregi nenule din intervalul [-100, 100] și se garantează că aceste șiruri reprezintă poligoane drepte.
• Într-un poligon drept laturile nu au puncte comune, exceptând capetele laturilor adiacente.
• Prima și ultima latură ale unui poligon drept sunt perpendiculare.

Exemplul 1

drept.in

1 2 8 5 3 -3 -1 2 -1 -4 -1 8 -2 1 3 1 -4 -3 2 1

drept.out

1 0 Explicație

Exemplul 2

drept.in

2 2 8 5 3 -3 -1 2 -1 -4 -1 4 1 1 -1 -1

drept.out

9 1

Rezolvare

with open("drept.in", "r") as fin:
    C, T = map(int, fin.readline().split())
    results = []
    for _ in range(T):
        n = int(fin.readline().strip())
        polygon = list(map(int, fin.readline().split()))
        
        is_polygon = True
        for i in range(n):
            if polygon[i] == 0:
                is_polygon = False
                break
            if i % 2 == 0:
                if polygon[i] < 0:
                    is_polygon = False
                    break
            else:
                if polygon[i] > 0:
                    is_polygon = False
                    break
        
        if C == 1:
            results.append(1 if is_polygon else 0)
        elif C == 2:
            area = 0
            for i in range(0, n, 2):
                area += abs(polygon[i]) * abs(polygon[i + 1])
            results.append(area)
        
    with open("drept.out", "w") as fout:
        fout.write(" ".join(map(str, results)))