Pagini recente » Cod sursa (job #549921) | Cod sursa (job #1109329) | Cod sursa (job #1122890) | Cod sursa (job #1143825) | Cod sursa (job #3295199)
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()