Pagini recente » Cod sursa (job #694119) | Cod sursa (job #2570122) | Cod sursa (job #1828055) | Cod sursa (job #564339) | Cod sursa (job #2883689)
def tokyoDrift(p, q, r):
def dete(a):
return (a[0][0] * (a[1][1] * a[2][2] - a[2][1] * a[1][2])
- a[1][0] * (a[0][1] * a[2][2] - a[2][1] * a[0][2])
+ a[2][0] * (a[0][1] * a[1][2] - a[1][1] * a[0][2]))
xs = [[1, 1, 1], [p[0], q[0], r[0]], [p[1], q[1], r[1]]]
det = dete(xs)
if det > 0:
return -1 # la dreapta
return 1 # stanga / colinear
with open('infasuratoare.in') as f:
n = int(f.readline())
points = []
for i in range(n):
points.append([float(x) for x in f.readline().split()])
def cmp(xs):
return xs[0], xs[1]
def getInf(xs):
stek = [xs[0],xs[1]]
for i in range(2, len(points)):
stek.append(points[i])
while len(stek) > 2 and tokyoDrift(stek[-3], stek[-2], stek[-1]) < 0:
stek.pop(-2)
return stek
points.sort(key=cmp)
jos = getInf(points)
reversedPoints = points[::-1]
sus = getInf(reversedPoints)
convexHull = jos
for i in sus:
if i not in convexHull:
convexHull.append(i)
with open('infasuratoare.out','w') as g:
g.write(str(len(convexHull)) + '\n')
for i in convexHull[::-1]:
g.write(str(i[0]) + ' ' + str(i[1])+'\n')