Competitive programming in Haskell: folding folds | blog :: Brent -> [String]

submited by
Style Pass
2021-06-24 08:00:03

Now that the semester is over—and I will be on sabbatical in the fall!—you can expect a lot more competitive programming in Haskell posts. In a previous post, I challenged you to solve Origami. j0sejuan took me up on the challenge, as did Aaron Allen and Ryan Yates; if you still want to try it, go do it before reading on!

In the problem, we start with a square sheet of paper and are given a series of folds to perform in sequence; each fold is specified as a line, and we fold whatever is on one side of the line across onto the other side. Given some query points, we have to compute how thick the resulting origami design is at each point.

The first order of business is some computational geometry relating to lines in 2D (this code can all be found in Geom.hs. Here I am following Victor Lecomte’s excellent Handbook of geometry for competitive programmers, which I think I’ve mentioned before. I’ll try to give a bit of explanation, but if you want full explanations and proofs you should consult that document.

The equation of a line can be thought of as the set of all points whose dot product with the vector is a constant . This will in fact be a line perpendicular to the vector , where determines the distance of the line from the origin. Alternatively, we can think of the vector , which is perpendicular to and thus parallel to the line; the line now consists of all points whose 2D cross product with is the constant (since ; note that the order matters). Either representation would work, but I will follow Lecomte in choosing the second: we represent a line by a vector giving its direction, and a scalar offset.

Leave a Comment
Related Posts