Cod sursa(job #2486532)

Utilizator gabrielmGabriel Majeri gabrielm Data 3 noiembrie 2019 02:11:24
Problema Infasuratoare convexa Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.25 kb
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    @staticmethod
    def read(f):
        x, y = map(float, next(f).split())
        return Point(x, y)

    def __lt__(self, other):
        return (self.x, self.y) < (other.x, other.y)

    def __sub__(self, other):
        return Point(self.x - other.x, self.y - other.y)

    def __repr__(self):
        return f'{self.x} {self.y}'


def cross_product(u, v):
    return u.x * v.y - u.y * v.x

def orientation_test(a, b, c):
    return cross_product(b - a, c - a)


def left_turn(a, b, c):
    return orientation_test(a, b, c) > 0


def right_turn(a, b, c):
    return orientation_test(a, b, c) < 0


def compute_hull(turn_fn):
    hull = [points[0], points[1]]

    i = 2
    while i < len(points):
        hull.append(points[i])
        while len(hull) >= 3 and not turn_fn(hull[-3], hull[-2], hull[-1]):
            hull.pop(-2)
        i += 1

    return hull


fin = open('infasuratoare.in')

n = int(next(fin))

points = [Point.read(fin) for _ in range(n)]

points.sort()

lower_hull, upper_hull = compute_hull(left_turn), compute_hull(right_turn)

upper_hull.reverse()

hull = lower_hull + upper_hull[1:]

with open('infasuratoare.out', 'w') as fout:
    print(*hull, sep='\n', file=fout)