Pagini recente » Cod sursa (job #1297539) | Cod sursa (job #1994548) | Cod sursa (job #2582145) | Cod sursa (job #2599998) | Cod sursa (job #2486532)
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)