b.py (1097B)
1 import fileinput 2 3 with fileinput.input() as lines: 4 a = [tuple(int(x) for x in l[:-1].split(',')) for l in lines] 5 6 # Check if the border is turning clockwise or counter-clockwise 7 def dir(p, q): 8 return p[0]*q[1]-p[1]*q[0] 9 t = 0 10 for i in range(len(a)): 11 p, q, r = a[i%len(a)], a[(i+1)%len(a)], a[(i+2)%len(a)] 12 t += 1 if dir((q[0]-p[0],q[1]-p[1]), (r[0]-q[0],r[1]-q[1])) > 0 else -1 13 14 def lbreaks(p, q, tl, br): 15 # Adjust for horizontal or vertical 16 (tt, z) = (t, 0) if p[0] == q[0] else (-t, 1) 17 18 if min(p[1-z], q[1-z]) >= br[1-z] or max(p[1-z], q[1-z]) <= tl[1-z]: 19 return False 20 if p[z] == tl[z]: 21 return tt * (q[1-z]-p[1-z]) > 0 22 if p[z] == br[z]: 23 return tt * (q[1-z]-p[1-z]) < 0 24 25 return p[z] > tl[z] and p[z] < br[z] 26 27 def admissible(a, i, j): 28 tl = (min(a[i][0], a[j][0]), min(a[i][1], a[j][1])) 29 br = (max(a[i][0], a[j][0]), max(a[i][1], a[j][1])) 30 return not any(lbreaks(a[k], a[(k+1)%len(a)], tl, br) for k in range(len(a))) 31 32 s = 0 33 for i in range(len(a)): 34 for j in range(i+1, len(a)): 35 if admissible(a, i, j): 36 s = max(s, (abs(a[i][0]-a[j][0])+1)*(abs(a[i][1]-a[j][1])+1)) 37 print(s)