Pagini recente » Cod sursa (job #2749485) | Cod sursa (job #1095447) | Cod sursa (job #890369) | Cod sursa (job #709164) | Cod sursa (job #3295198)
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()