Challenge #6

It's becoming clear that your troubles with Eos are not over. With what you learned from Watu about Eos' activities still fresh in your mind, you continue your journey. After several quiet hours, something ahead nearly makes your bones leap from your skin. A tree is moving.

You blink and try to adjust your eyes, but definitely one of the tall, bark-covered shapes is unmistakably walking, shuffling carefully through the underbrush. Being the valiant and brave space explorer you are, you approach with caution and call out. The tree turns.

It is exactly what you feared: a boy made of tree… or a tree made of boy. His wooden brows lift and his leaves rustle as he responds.

"My name is Treeboy," he says. His friendly tone assures you that you have nothing to fear. And then he tells you his story.

As a young child, Treeboy was slothful and unhelpful, refusing any task asked of him. A wicked shaman, losing patience, planted a seed in his chest that grew and fused with the boy until bark replaced skin, branches replaced limbs, and he stood as he is now. The shaman gave him only one way to become human again: Help as many people as possible.

Treeboy devoted himself to the task with earnest determination, wandering the land and offering aid wherever he could. But being a walking tree has its disadvantages. In the deep woods, a frightened woodcutter mistook him for a monster and severed one arm with a single terrified swing. Much later, a cruel prankster set fire to him, scorching the other arm beyond saving. Both arms were eventually lost, leaving Treeboy without the limbs he once used to help so many.

His voice grew heavy. "Now I fear I cannot help people anymore. And if I cannot help… I will never become myself again." You assure him you will do anything you can. To your relief, Treeboy nods.

"There is something you can do. While I still had my arms, most of the help I gave was pulling people out of the many tar pits scattered across this region. These tar pits sometimes can be hard to spot and a great many people fail to notice them, falling in and getting stuck. Without arms, I can't save anyone who falls in. But I've had a great idea. If we can build a barrier around all the tar pits, no one will ever stumble in by accident."

He tilts his wooden head toward a large bark-etched map inside the pouch strapped to his torso. Dozens of x, y coordinate points representing tar pit locations, your puzzle input.

"To keep costs low, the barrier must be as efficient as possible. Posts are cheap, but not that cheap. A fence that constantly bends inward wastes posts. So the barrier must be shaped as the convex hull of all the tar pits." You raise a brow. Treeboy explains further. "Imagine stretching a rope tightly around all these tar pit points. Pull it until it is taught and can't bend inward anymore. The shape the rope forms (smooth, bulging outward, no indents) that's the convex hull. The posts go at every corner of that hull." If more than 2 tar pits lie along the same straight edge, only the outer two corners need posts. Any other tar pits resting along that straight line do not count as an additional post.

He taps the map with the stump of his arm. "To get the cost of building the barrier, we multiply two things: The number of posts we need (that is, the number of vertices of the convex hull) and the total number of tar pits contained within that hull, including those that lie exactly on the boundary.
So… final price = number of posts × tar pits contained."

You look over the map more closely. Treeboy continues, grateful to have someone listening.

"Finding the hull is easy once you know how. As you walk around the perimeter, you are connecting the leftmost tar pits from your perspective, like you're wrapping paper around a gift." The explanation is surprisingly elegant. You can picture the shape forming.

"If you can compute this," Treeboy pleads, "I can order the right amount of posts. And then no one will fall into the tar again. That… would be helping people. Truly helping." You smile. After all you have survived, after all that Eos and fate have thrown at you, helping a boy-tree regain hope suddenly feels like the most natural thing in the world. You take the map. Time to determine the cost that will help Treeboy continue his noble mission.

For example:

With tar pits at points: 0,4
1,1
2,3
3,0
1,6
2,5
1,4
4,5

Your map of the tar pits
would look like this:

And the convex hull
would look like this:

This means there are 5 posts and 8 total tar pits, making the final cost to build the barrier ⅊40.

Here is your map: