Meltdown
Time limit1sMemory limit128 MB
A polygon is lowered into a dissolving liquid at speed v while its sides erode at speed c; find when the liquid first reaches a given interior point.
- Level
Hard8 of 10
- Topics
- Geometry, Binary search, Simulation
- Solved
- No attempts yet
Problem
A polygon is lowered from the air into a liquid at a constant speed of metres per minute. The liquid dissolves the polygon from all of its sides at a constant speed of metres per minute. Given a point inside the polygon that moves together with the polygon, determine when the liquid first reaches that point.
The border between the air and the liquid always has -coordinate , and the liquid eats away at the polygon from its sides in two dimensions. The polygon does not rotate as it is lowered, and at time it is not yet touching the liquid.
Unlike the polygon, which is flat (two-dimensional), the liquid exists in three dimensions, so it seeps into concave cavities of the polygon. For example, if the polygon is 'cup-shaped', the liquid can get 'inside' the cup.
Input
The input consists of several test cases.
The first line of each test case contains five integers , , , , and , where , , , and .
Each of the next lines contains one vertex of the polygon. The -th line contains two integers and (, ).
The vertices are given in counter-clockwise order. The border of the polygon does not intersect or touch itself, and the point lies strictly inside the polygon (it is not on the border).
The input is terminated by a line containing 0 0 0 0 0. These zeros are not a test case and must not be processed.
Output
For each test case, output the first time, in minutes, that the liquid reaches the specified point, rounded to four decimal places.