b-fixed.py (1428B)
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 external_by_vertex(a, i, j): 15 p = tuple(a[(i+1)%len(a)][k] - a[i][k] for k in range(2)) 16 q = tuple(a[j][k] - a[i][k] for k in range(2)) 17 18 return t * dir(p, q) < 0 19 20 def lbreaks(p, q, tl, br): 21 # Adjust for horizontal or vertical 22 (tt, z) = (t, 0) if p[0] == q[0] else (-t, 1) 23 24 if min(p[1-z], q[1-z]) >= br[1-z] or max(p[1-z], q[1-z]) <= tl[1-z]: 25 return False 26 if p[z] == tl[z]: 27 return tt * (q[1-z]-p[1-z]) > 0 28 if p[z] == br[z]: 29 return tt * (q[1-z]-p[1-z]) < 0 30 31 return p[z] > tl[z] and p[z] < br[z] 32 33 def admissible(a, i, j): 34 # Fix (see ../README.md): check given vertices to determine if the 35 # rectangle is fully external to the figure. 36 if external_by_vertex(a, i, j): 37 return False 38 39 tl = (min(a[i][0], a[j][0]), min(a[i][1], a[j][1])) 40 br = (max(a[i][0], a[j][0]), max(a[i][1], a[j][1])) 41 return not any(lbreaks(a[k], a[(k+1)%len(a)], tl, br) for k in range(len(a))) 42 43 s = 0 44 for i in range(len(a)): 45 for j in range(i+1, len(a)): 46 if admissible(a, i, j): 47 s = max(s, (abs(a[i][0]-a[j][0])+1)*(abs(a[i][1]-a[j][1])+1)) 48 print(s)