Cod sursa(job #3295197)

Utilizator tudorbuhniaTudor Buhnia tudorbuhnia Data 3 mai 2025 14:52:26
Problema Infasuratoare convexa Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.04 kb
def convex_hull(points):

    points.sort()

    if len(points) <= 1:
        return points

    def cross(o, a, b):
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

    lower = []
    for p in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)

    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)

    return lower[:-1] + upper[:-1]


with open('infasuratoare.in', 'r') as file:
    lines = file.readlines()

n = int(lines[0])

# P = []
# for k in lines[1:]:
#     kk = k.strip().split()
#     P.append((float(kk[0]), float(kk[1])))

P = [tuple(map(float, line.strip().split())) for line in lines[1:n+1]]

# print(P)

f = open("infasuratoare.out", "w")

v = convex_hull(P)

f.write(str(len(v)) + "\n")
for k in v:
    f.write(str(k[0]) + " " + str(k[1]) + "\n")
    # print(k[0], k[1])

f.close()