Rods

Time limit1sMemory limit128 MB

Summary

For each rod, compute the distance from the chord midpoint to the arc midpoint after it bends into a circular arc of given arc length and chord length, rounded to an integer.

Level: Medium7 of 10
Topics: Geometry, Binary search, Math
Solved: No attempts yet

Problem

A laboratory at a certain company is testing a new material called politoksyparen. During the research an interesting property was discovered: a straight rod made of this material, when heated, lengthens and bends so that it turns into a circular arc whose chord is the rod's original straight shape (this property holds only for rods of very small diameter).

Suppose there are $n$ rods of very small diameter, where the $i$ -th rod has initial length $l_i$ ( $1 \le l_i \le 100\,000$ ). When heated, each rod lengthens by $d_i$ ( $1 \le d_i \le 100$ , with $d_i \le l_i / 2$ ). Lengths are measured in millimeters.

Write a program that:

reads from standard input the number of rods $n$ and, for each rod, its length $l_i$ and its increase in length $d_i$ ;
for each rod, computes the distance between the midpoint of the chord and the midpoint of the arc after heating (assuming the rod really bends into a circular arc); the answer must be an integer that differs from the exact value by at most $0.5$ ;
writes the results to standard output.

Input

The first line contains one positive integer $n$ ( $n \le 50\,000$ ). Each of the next $n$ lines contains two integers separated by a single space: the original length of the rod $l_i$ and its increase in length while heated $d_i$ .

Output

Print $n$ lines, each containing one nonnegative integer. The integer on the $i$ -th line must equal the distance between the position of the midpoint of the $i$ -th rod before and after heating, computed to the required accuracy.

Examples3

Example 1
Input
```
2
1000 20
15000 10
```
Expected output
```
87
237
```
Example 2
Input
```
1
2 1
```
Expected output
```
1
```
Example 3
Input
```
1
100 50
```
Expected output
```
46
```