Pagini recente » Cod sursa (job #2147350) | Cod sursa (job #149639) | Cod sursa (job #1424690) | Istoria paginii runda/3uqjey4/clasament | Cod sursa (job #3295196)
def convex_hull(points):
points = sorted(points)
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)
return lower[:-1] + upper[:-1]
with open('infasuratoare.in', 'r') as file:
lines = file.readlines()
n = int(lines[0])
P = []
for k in lines[1:]:
kk = k.strip().split()
P.append((float(kk[0]), float(kk[1])))
# print(P)
f = open("infasuratoare.out", "w")
v = convex_hull(P)
f.write(str(len(v)) + "\n")
for k in v:
f.write(str(k[0]) + " " + str(k[1]) + "\n")
# print(k[0], k[1])
f.close()