Too Much Water
InterviewTime limit1sMemory limit128 MB
Given a property point, compute the hour when the growing semicircle centered at the origin first covers it, using the fixed 50 square meters per hour rate.
- Level
Easy3 of 10
- Topics
- Geometry, Math, Binary search, Implementation
- Solved
- No attempts yet
Problem
Fred Mapper is a real estate agent in Prague. Many foreign delegates attending the NATO Summit ask him to find a house to rent during their stay in Prague, and some plan to stay for a longer time even after the Summit ends. Unfortunately, many of them saw pictures on TV of the floods that happened in August, and they are afraid of water.
Many of Fred's properties are located in Kampa. While investigating the August data, he learned that during a flood the water covers exactly square meters each hour. We now need to determine how much time is available for evacuation at any given point.

After further research, Fred learned that the flooded land forms a semicircle. This semicircle is the part of a circle centered at that lies above the x-axis, which bisects the circle. Locations below the x-axis are in the river. The semicircle has area at the beginning of hour (when the flood begins), as illustrated in the figure.
Input
The input consists of several property descriptions. Each property is described by one line containing two numbers and , the Cartesian coordinates of the property. and are floating-point numbers measured in meters, given with one digit after the decimal point, with and .
The point is never given as a property, except on the last line, where two zeros terminate the input. This last line must not be processed.
Output
For each property, print a single line of the form "The property will be flooded in hour Z.", where is the first hour (counted from ) at the end of which this property lies within the semicircle. must be an integer. No property lies exactly on the semicircle boundary at the end of any hour; it is always either strictly inside or strictly outside.