Cod sursa(job #2883689)

Utilizator HadircaDionisieHadirca Dionisie HadircaDionisie Data 1 aprilie 2022 18:18:26
Problema Infasuratoare convexa Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.22 kb
def tokyoDrift(p, q, r):
    def dete(a):
        return (a[0][0] * (a[1][1] * a[2][2] - a[2][1] * a[1][2])
                - a[1][0] * (a[0][1] * a[2][2] - a[2][1] * a[0][2])
                + a[2][0] * (a[0][1] * a[1][2] - a[1][1] * a[0][2]))

    xs = [[1, 1, 1], [p[0], q[0], r[0]], [p[1], q[1], r[1]]]

    det = dete(xs)

    if det > 0:
        return -1  # la dreapta

    return 1  # stanga / colinear


with open('infasuratoare.in') as f:
    n = int(f.readline())

    points = []

    for i in range(n):
        points.append([float(x) for x in f.readline().split()])


def cmp(xs):
    return xs[0], xs[1]

def getInf(xs):
    stek = [xs[0],xs[1]]

    for i in range(2, len(points)):
        stek.append(points[i])
        while len(stek) > 2 and tokyoDrift(stek[-3], stek[-2], stek[-1]) < 0:
            stek.pop(-2)

    return stek

points.sort(key=cmp)
jos = getInf(points)
reversedPoints = points[::-1]
sus = getInf(reversedPoints)

convexHull = jos
for i in sus:
    if i not in convexHull:
        convexHull.append(i)

with open('infasuratoare.out','w') as g:
    g.write(str(len(convexHull)) + '\n')
    for i in convexHull[::-1]:
        g.write(str(i[0]) + ' ' + str(i[1])+'\n')