(Basis for J. Robert Dorfman Prize for Numerical Computation)
Scientists and engineers frequently use a method known as finite differencing to iteratively compute numerical solutions to partial differential equations. We adapt a similar method to calculate heat diffusion in a metal sheet.
A rectangular sheet of metal is heated at its edges so that the edges always remain at a constant 100 degrees. As heat diffuses through the sheet, some heat is radiated away.
The sheet is nonuniform, so heat is lost at a different rate at each location. For most areas of the sheet, in the time it takes heat to diffuse through a 1 cm2 block, 1% of the heat is lost. In areas containing impurities, 10% of the heat is lost. For this problem assume that 1% heat loss reduces a temperature of x degrees to 0.99x degrees, and that a 10% heat loss reduces x degrees to 0.9x degrees.
For each point on the metal sheet, the temperature of a 1 cm2 block can be calculated as the average of the temperatures of its top, bottom, left, and right 1 cm2 blocks, each reduced by its heat loss. By applying the formula to each point on the metal sheet, you can calculate the temperature of the sheet at a given instant in time as heat diffuses through the sheet. By repeating the process, you can calculate the temperature of the sheet as it changes over time and converges to a steady state.
The goal of the problem is calculate the diffusion of heat through the metal sheet, then determine the temperature of some point in the sheet when it stablizes at a steady state. For this problem we'll assume the sheet is in steady state when no part of the sheet changes its temperature by more than the specified tolerance after applying the heat diffusion formula.
The following figure shows the temperature for each 1 cm2 block of a 4 by 5 cm sheet at steady state (tolerance 0.00000001) when an impurity is found at (2,2). Note that the edges of the sheet always remain at 100.0 degrees.
Hint: The initial temperature of the sheet and the order the formula is applied do not affect the eventual steady-state solution, only the speed at which it is reached. Choosing good initial temperatures for each point in the sheet (close to the steady-state solution) and a good evaluation order (speeding up movement towards the steady-state solution) will thus reduce overall computation time.
The first line contains x, y, the length and height of the sheet in cm. The second line contains x1, y1, the coordinates of the query point in cm (assume points in the sheet lie between (1,1) and (x,y)). The third line contains the size of the tolerance used to detect steady state as a floating point number. It is followed by a number of lines listing the coordinates of impurities in the sheet, in cm. A line containing a pair of zeros indicates end of input. You may assume the largest sheet is 50 by 50 cm, and that variables of type real will be sufficiently precise to calculate the desired temperature.
The first line should be the temperature calculated for the query point, with precision up to six decimal places. The second line should be the number of times you recalculated the temperature of the metal sheet (this will not affect correctness of the result).
| Input: | Output: |
|---|---|
10 10 5 5 0.00000001 4 2 1 3 3 2 0 0 |
77.750039 140 |
| Input 1 | Output 1 |
|---|---|
| Input 2 | Output 2 |
| Input 3 | Output 3 |
| Input 4 | Output 4 |
| Input 5 | Output 5 |