0931 - Sortare Unghi

Cerința

Se dau puncte distincte în plan. Asociem fiecărui punct semidreapta care pornește din originea sistemului de coordonate și trece prin acel punct. Să se afișeze punctele în ordine crescătoare a unghiului pe care semidreapta asociată îl face cu semidreapta spre plus infinit a axei OX. Dacă două unghiuri sunt egale se va afișa punctul cel mai apropiat de origine.

Date de intrare

Fișierul de intrare sortareunghiIN.txt conține pe prima linie n, reprezentând numărul de puncte. Pe următoarele n linii se găsesc câte două numere separate printr-un spațiu, reprezentând abscisa respectiv ordonata câte unui punct.

Date de ieșire

Fișierul de ieșire sortareunghiOUT.txt va conține n linii cu câte două numere separate prin câte un spațiu, reprezentând abscisa respectiv ordonata câte unui punct, în ordinea cerută.

Restricții și precizări

• 1 ≤ n ≤ 100
• Numerele din fișierul de intrare sunt întregi cuprinse între -1001 și 1001.
• Unghiurile sunt în intervalul [0,360).

Exemplul 1

sortareunghiIN.txt:

3

1 1

-1 -1

-1 1

sortareunghiOUT.txt:

1 1

-1 1

-1 -1

Exemplul 2

sortareunghiIN.txt:

101

1 1

-1 -1

-1 1

Output:

Error: n should be between 1 and 100.

Exiting due to constraint violations.

Rezolvare

import math

class Element:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def check_constraints(n, elements):
    if not 1 <= n <= 100:
        print("Error: n should be between 1 and 100.")
        return False
    
    for elem in elements:
        if not -1001 <= elem.x <= 1001 or not -1001 <= elem.y <= 1001:
            print("Error: Element coordinates should be between -1001 and 1001.")
            return False

    return True

def distance(a):
    return a.x ** 2 + a.y ** 2

def read_elements():
    elements = []

    try:
        with open("sortareunghiIN.txt", "r") as file:
            n = int(file.readline())
            for _ in range(n):
                line = file.readline().strip()
                if line:
                    x, y = map(int, line.split())
                    elements.append(Element(x, y))
    except ValueError:
        print("Error: Incorrect input format.")
        return 0, []

    return n, elements

def print_elements(elements):
    with open("sortareunghiOUT.txt", "w") as file:
        for elem in elements:
            file.write(f"{elem.x} {elem.y}\n")

def angle(a):
    if a.x > 0 and a.y > 0:
        return 1.0 * a.y / a.x
    elif a.x < 0 and a.y > 0:
        return 10000 + 1.0 * (-a.x) / a.y
    elif a.x < 0 and a.y < 0:
        return 20000 + 1.0 * a.y / a.x
    elif a.x > 0 and a.y < 0:
        return 30000 + 1.0 * a.x / (-a.y)
    elif a.x == 0:
        if a.y > 0:
            return 10000
        else:
            return 30000
    elif a.y == 0:
        if a.x > 0:
            return 0
        else:
            return 20000

def compare(a, b):
    return angle(a) < angle(b) or (angle(a) == angle(b) and distance(a) < distance(b))

def main():
    n, elements = read_elements()

    if n > 0 and check_constraints(n, elements):
        elements.sort(key=lambda x: (angle(x), distance(x)))
        print_elements(elements)
    else:
        print("Exiting due to constraint violations.")

if __name__ == "__main__":
    main()