commit 4dc2097b38697614dba7a58bf2ec53e1e54e52fe
parent e87e83de464a2ee47d020fbe532f6f558fa83369
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue, 9 Dec 2025 21:46:42 +0100
Fixed part 2 for edge cases not present in input file
Diffstat:
2 files changed, 73 insertions(+), 0 deletions(-)
diff --git a/2025/09/b-fixed.py b/2025/09/b-fixed.py
@@ -0,0 +1,48 @@
+import fileinput
+
+with fileinput.input() as lines:
+ a = [tuple(int(x) for x in l[:-1].split(',')) for l in lines]
+
+# Check if the border is turning clockwise or counter-clockwise
+def dir(p, q):
+ return p[0]*q[1]-p[1]*q[0]
+t = 0
+for i in range(len(a)):
+ p, q, r = a[i%len(a)], a[(i+1)%len(a)], a[(i+2)%len(a)]
+ t += 1 if dir((q[0]-p[0],q[1]-p[1]), (r[0]-q[0],r[1]-q[1])) > 0 else -1
+
+def external_by_vertex(a, i, j):
+ p = tuple(a[(i+1)%len(a)][k] - a[i][k] for k in range(2))
+ q = tuple(a[j][k] - a[i][k] for k in range(2))
+
+ return t * dir(p, q) < 0
+
+def lbreaks(p, q, tl, br):
+ # Adjust for horizontal or vertical
+ (tt, z) = (t, 0) if p[0] == q[0] else (-t, 1)
+
+ if min(p[1-z], q[1-z]) >= br[1-z] or max(p[1-z], q[1-z]) <= tl[1-z]:
+ return False
+ if p[z] == tl[z]:
+ return tt * (q[1-z]-p[1-z]) > 0
+ if p[z] == br[z]:
+ return tt * (q[1-z]-p[1-z]) < 0
+
+ return p[z] > tl[z] and p[z] < br[z]
+
+def admissible(a, i, j):
+ # Fix (see ../README.md): check given vertices to determine if the
+ # rectangle is fully external to the figure.
+ if external_by_vertex(a, i, j):
+ return False
+
+ tl = (min(a[i][0], a[j][0]), min(a[i][1], a[j][1]))
+ br = (max(a[i][0], a[j][0]), max(a[i][1], a[j][1]))
+ return not any(lbreaks(a[k], a[(k+1)%len(a)], tl, br) for k in range(len(a)))
+
+s = 0
+for i in range(len(a)):
+ for j in range(i+1, len(a)):
+ if admissible(a, i, j):
+ s = max(s, (abs(a[i][0]-a[j][0])+1)*(abs(a[i][1]-a[j][1])+1))
+print(s)
diff --git a/2025/README.md b/2025/README.md
@@ -148,3 +148,28 @@ and in fact I wasted a lot of time searching a quadratic or O(n^2log n)
solution before I focused on formalizing a cubic one. The problem is that
I did not have smaller inputs to try my code against, so I this solution
was too slow I did not have any way to check that it was at least correct.
+
+EDIT (about 12h after solving part 2): apparently my algorithm is not
+entirely correct. In particular, it can fail by selecting a rectangle
+that is completely external to the figure and none of whose sides overlaps
+any of the lines.
+
+For example with this input:
+
+```
+101,51
+101,0
+0,0
+0,2
+1,2
+1,1
+100,1
+100,50
+99,50
+99,51
+101,51
+```
+
+The first version of my program return 4851 instead of 202. I added a
+check for this case in `b-fixed.py`, hopefully it works in 100% of the
+cases now.
