this post was submitted on 10 Dec 2024
6 points (100.0% liked)

NotAwfulTech

386 readers
5 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
 

The previous thread has fallen off the front page, feel free to use this for discussions on current problems

Rules: no spoilers, use the handy dandy spoiler preset to mark discussions as spoilers

you are viewing a single comment's thread
view the rest of the comments
[–] [email protected] 3 points 1 week ago* (last edited 1 week ago)

Day 12:

P1Ok. 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.

P2It 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.