# 2010 ECOO Competition Q1: Connect the Dots
# JW & AH
from math import *
from operator import *
# Separate points to the left of the centre and to the right of the centre.
# Sort by slope from centre to point: As you go ccw from the 12:00 position,
# slopes go from really negative to really positive. Slopes 'reset' at 6:00,
# but the pattern still follows: do the two sides separately and put them
# together later.
def angles2(center, points):
left = []
right = []
for p in points:
if p[0] <= center[0]:
left.append(p+[(center[1]-p[1])/(center[0]-p[0])])
else:
right.append(p+[(center[1]-p[1])/(center[0]-p[0])])
left.sort(key=itemgetter(2))
right.sort(key=itemgetter(2))
return left + right + [left[0]]
def cofb(points):
lp=float(len(points))
xtot = sum([x[0] for x in points])
ytot = sum([y[1] for y in points])
return (xtot/lp, ytot/lp)
f = open("data11.txt", 'r')
for case in range(5):
sides = int(f.readline())
points = []
for s in range(sides):
points.append(map(float, f.readline().rstrip().split(' ')))
orderedp = angles2(cofb(points), points)
dprod = 0
uprod=0
# multiply diagonal down
for i in range(sides):
dprod += orderedp[i][0] * orderedp[i+1][1]
uprod += orderedp[i][1] * orderedp[i+1][0]
area = abs(dprod - uprod)/2.0
print "The area of the %d sided polygon is %.1f" % (sides, area)