Magical Island
Time limit8sMemory limit512 MB
Four crystals at the corners of a W by H rectangle each project a same-radius circular shield; find the minimum radius so the four circles cover area S, and output 4R^2.
- Level
Medium6 of 10
- Topics
- Geometry, Binary search, Math, Implementation
- Solved
- No attempts yet
Problem
This is a story set in the epoch of magic. A clan of magicians lived on an artificial island built by magic power.
One day, a crisis erupted on the island. An empire called ACM (Atlas Country of Magic) demanded unconditional surrender, and otherwise its army would attack the island with magical missiles. The clan was too proud to surrender, so it built a system to generate magical shields that would protect the clan from the threat of magical missiles. In this system, a crystal of a different element was placed on each corner of the island. The world consisted of four elements: Fire, Water, Air, and Earth. Each crystal received magic power from the magicians and generated a magical shield of its own element, shielding the island from magical missiles of the same element. Every magical missile consisted of one of the four elements. A magical shield covered a circular area, and the crystal had to be located at the center of that circular area. The crystal required R2 magic power to shield a circular area of radius R. There was one restriction, however. The magicians had to send exactly the same amount of magic power to all crystals, because otherwise the balance among the four elements would break and the island would be lost.
The clan decided to live in an area that is shielded from any magical missile. Write a program that calculates the minimum amount of magic power needed to secure enough area for them to live in.
Input
The input consists of multiple datasets. Each dataset is a single line containing three integers W, H, and S, separated by a single space. The line containing three zeros separated by a single space indicates the end of the input.
W and H are the width and depth of the island, respectively. S is the area the magicians need to live in. You may assume that 0 < W, H ≤ 100 and 0 < S ≤ W × H.
Output
For each dataset, output the total minimum necessary magic power on a separate line. The value may contain an error less than or equal to 0.001. You may print any number of digits after the decimal point.