Limits 1s, 512 MB

Fisaow is a farmer. He has a large field covered with grass and wants to create some pattern or design in that field by removing grasses at certain places so that it looks like a crop circle from the sky. But he is not familiar with geometric shapes. One day he noticed that when a cow eats grass in the fields, it creates different geometric shapes based on how they are tied in the field.

Now he has NN cows and NN ropes. For every cow he will use 2 points AiA_i and BiB_i to tie it up. That means, one end of the rope will be tied to point AiA_i and the other end to BiB_i. Every cow has a metal ring around its neck and the rope will go through the metal ring such a way that the cow can move freely (see the picture: there is no knot with the ring). The cows will eat grass from wherever it can go. The amount of grass each cow can eat is the area that each cow can cover.

Now Fisaow has given you the points AiA_i (X1,Y1)(X_1, Y_1) and BiB_i (X2,Y2)(X_2, Y_2) the length of the ropes LiL_i for each of the NN cows. Help him to find the maximum amount of grass each cow can eat.

Note: Distance(Ai,Bi)Li\text{Distance}(A_i, B_i) ≤ L_i.


Input starts with an integer NN (0<N1000000 < N ≤ 100000), the number of cows. The next NN lines will have 5 space separated integers X1X_1, Y1Y_1, X2X_2, Y2Y_2, (106X1,Y1,X2,Y2106-10^6 ≤ X_1, Y_1, X_2, Y_2 ≤ 10^6), coordinates of the two points, and LL (0L1070 \le L ≤ 10^7), the length the each rope.


For each cow, print the maximum amount of grass it can eat in separate lines. Absolute errors less than 10610^{-6} will be ignored.


0 0 6 0 10
-4 3 8 3 20
-5 6 5 6 26
-3 -6 -3 -18 20


Login to submit.


94% Solution Ratio
mahdi.hasnatEarliest, Dec '19
Kuddus.6068Fastest, 0.1s
mahdi.hasnatLightest, 1.4 MB
RafeedShortest, 175B
Toph uses cookies. By continuing you agree to our Cookie Policy.