this post was submitted on 10 Dec 2024
6 points (100.0% liked)
NotAwfulTech
385 readers
3 users here now
a community for posting cool tech news you don’t want to sneer at
non-awfulness of tech is not required or else we wouldn’t have any posts
founded 1 year ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
Day 12:
P1
Ok. I have been traumatised by computational geometry before, so I was initially spiralling. Luckily, there wasn't too much comp geo stuff to recall.My solution was a lot simpler than I initially thought: no need for union-find, accounting for regions inside regions, etc. Just check every square for a given region, and if it touches a square in the same region that you've seen before, subtract the common edge. This is linear in the area of the problem, so it's fast enough.
P2
It took a moment to figure out that I could modify the above perimeter counting to mark the squares containing the perimeter and walk along it afterwards, counting each edge. This is also linear in area.