Cod sursa(job #3295198)

Utilizator tudorbuhniaTudor Buhnia tudorbuhnia Data 3 mai 2025 14:57:10
Problema Infasuratoare convexa Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.04 kb
def convex_hull(points):
    points.sort()  # In-place sorting

    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)

    # Combine and remove duplicate endpoint
    return lower[:-1] + upper[:-1]

def main():
    with open('infasuratoare.in', 'r') as file:
        n = int(file.readline())
        points = [tuple(map(float, file.readline().split())) for _ in range(n)]

    # print(points)

    hull = convex_hull(points)

    with open('infasuratoare.out', 'w') as out:
        out.write(f"{len(hull)}\n")
        for x, y in hull:
            out.write(f"{x} {y}\n")

if __name__ == "__main__":
    main()