Artifacts

Problem code: ALG09

All submissions for this problem are available.

John is a notorious theaf, popular for stealing artifacts. Once, being afraid of getting caught, he went into the forest to hide the stolen artifacts. As the forest was big, it was hard to remember and track the exact location of the hidden artifacts, so at the time of hiding he placed a device along with it, which can continuously send signal. John kept a similar device for himself that was paired with the hidden device and it could only measure the strength of the signal emitted by the device that was hidden. After ensuring his safety, John went to the forest again to retrieve the artifacts. Assuming that forest is spread over a rectangular area, let us say that John enters the forest at point (0,0), which is one of the corner points of forest. Now John moves randomly at different locations and if John moves to a location that is closer to the object than the previous location, the device starts beeping at faster rate and at slower rate if he moves farther away. The rate of beeping remains same if the distance remains same.

Input

1st line contains number of test cases.

1st line of each test case consist of two integers x and y,separated by spaces, where (x,y) is coordinate diagonally opposite to (0,0).

2nd line of test case contains an integer N, which is followed by N lines each containing three values a,b,c separated by spaces where (a,b) = location of John and c=1 if closer than the previous distance, -1 if farther away than the previous distance, 0 if John is at the same distance. (This N lines are in sequence, according to the movement of John)

Output

For each test case, output the area in which the artifact may be present for each of the N lines mentioned above(rounded to 2 decimal points). Output zero if there is no such area.

Example

Input:
1
50 50
4
50.0 50.0 -1
50.0 0.0 1
0.0 0.0 -1
50.0 50.0 1

Output:
1250.00
937.50
312.50
0.00

Author: illume
Date Added: 15-02-2011
Time Limit: 1 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions