Cod sursa(job #3295199)

Utilizator tudorbuhniaTudor Buhnia tudorbuhnia Data 3 mai 2025 15:16:00
Problema Infasuratoare convexa Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.09 kb
def convex_hull(points, n):

    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 i in range(0, n):

        while len(lower) >= 2 and cross(lower[-2], lower[-1], points[i]) <= 0:

            lower.pop()

        lower.append(points[i])



    upper = []

    for i in range(n-1, -1, -1):

        while len(upper) >= 2 and cross(upper[-2], upper[-1], points[i]) <= 0:

            upper.pop()

        upper.append(points[i])



    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)]



    hull = convex_hull(points, n)



    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()