P2452 [SDOI2005] Dragon-Slaying Legend - Dragon-Slaying Spear Scroll

The seer saw the herbs Xiuma had retrieved and nodded with satisfaction. He said to Xiuma, "Come with me." Xiuma obediently followed the seer into his room. The seer’s room was very large, with bookshelves on all sides, neatly lined with rows of books. In the center of the room, on a round table, stood a huge crystal ball, whose glow illuminated the entire chamber. The seer walked to a row of shelves and pulled out a thin book. It looked extremely old; the pages had turned yellow, and some parts were blackened. Xiuma thought, this book must be several hundred years old. The seer motioned for Xiuma to sit. He opened the book in his hand and said, "I have studied this book for a long time. It is written in an ancient script and records a very old legend. The book says that ordinary weapons cannot harm a dragon; only the Dragon-Slaying Spear forged by the gods together can destroy it. To prevent its abuse, the gods sealed the spear on Mount Kakisi. Only those with extraordinary courage, strength, and wisdom can break this seal. For hundreds of years, many tried to obtain the spear’s power, but none succeeded. I checked all records about the spear and carefully studied them. I learned that the spear is sealed in a temple on the mountaintop. To break the seal, one must push a huge round stone in the temple to the center of the altar and then chant the incantation that unlocks the seal." Xiuma asked, "That incantation must have been lost, right?" "No, quite the opposite," the seer said. "The incantation has always been recorded in this book and has been preserved intact." "Then all that remains is to push the round stone to the center of the altar," Xiuma smiled confidently. But the seer shook his head. "No, Xiuma, things are not as simple as you think. Climbing Mount Kakisi is not easy. It towers into the clouds, with bare rock walls all around and almost nowhere to set foot. Only a true warrior can climb it. That round stone is not easy to move either; it takes extraordinary strength. These things, Xiuma, you have. But if that were enough, someone would have already taken the spear. The book says one needs courage, strength, and wisdom. Wisdom is the real key. If you cannot push the round stone to the center of the altar within a fixed time, the stone will automatically roll back, and the person who pushed it will never be able to move it again. And no matter how hard you push, the stone cannot roll as fast as you might wish. I estimate that only by following the shortest route can you push the stone to the center within the time limit. The temple is filled with pillars of various sizes. Some gaps between pillars are narrow, and the stone simply cannot be pushed through. Because of all these difficulties, no one has been able to take the Dragon-Slaying Spear from the temple." Xiuma fell silent for a moment. "No matter what, I will try. If I cannot get the spear, then no one will." The seer nodded. "Go, Xiuma. Remember, use your wisdom." Xiuma rode for ten days and nights and finally reached the foot of Mount Kakisi. Just as the seer had said, there was no path up the mountain, and it was hard to find a foothold. Yet relying on his courage and skill, Xiuma climbed to the summit. When he entered the temple, he immediately saw the huge round stone. What should Xiuma do to push the stone to the center of the altar? ### Task Your task is to compute the length of the shortest route along which the round stone can be pushed to the center of the altar. Pushing it to the altar’s center means the center of the round stone coincides with the center of the altar. The initial position of the stone’s center and the altar’s center are given. The stone has radius $R$ and can roll in any direction. All pillars in the temple are right square prisms of various sizes. While pushing the stone, the distance from the stone’s center to every pillar must be at least $R$; otherwise, the stone will be blocked and cannot continue to roll.

The first line contains five real numbers, which are the $x$ and $y$ coordinates of the initial position of the stone’s center, the radius $R$ of the stone, and the coordinates $(x, y)$ of the altar’s center. The second line contains an integer $n$, the number of pillars in the temple. Each of the next $n$ lines contains three real numbers $(x_i, y_i, r_i)$, describing one pillar: the $x$ and $y$ coordinates of the lower-left corner of the $i$-th pillar and the side length of that pillar. All real numbers in the input are given with precision to $2$ decimal places and are within $0$ to $1000$ inclusive.

Output a single real number, the length of the shortest route needed to push the stone to the center of the altar, rounded to two decimal places. If there is no route to push the stone to the altar’s center, output `0.00`.

### Constraints and Conventions For all testdata, $0 \le n \le 20$. --- Xiuma pondered for a long time, then decisively walked to the round stone and pushed hard. Under his effort, the stone slowly rolled forward. From time to time, Xiuma adjusted the pushing direction so the stone would roll as he intended. At last, with a click, the stone settled steadily at the center of the altar. A beam of light shot down from the temple roof and enveloped the entire altar. Xiuma loudly recited the incantation that broke the seal. Instantly, the altar began to tremble, and the round stone in the middle swayed. Suddenly, the entire stone shattered completely. At the center of the altar appeared a spear. The shaft shimmered with a holy light, drawing awe and admiration. Xiuma stepped forward and drew the spear. He felt a surge of great power pass into his hands. With a casual sweep of the spear, there was a loud crash, and a huge stone pillar split into four pieces. Amazed and delighted, Xiuma knew this must be the Dragon-Slaying Spear. Translated by ChatGPT 5