OJ Board

does this problem have any critical input?
I got a lot WA for it.

EDIT : i got AC
use EPS=0.000001 for double comparison , i did this and got AC

I'm also repeatedly getting WA, and since this seems to be very simple problem, I'm starting to suspect that i missed something ;p

Basic math assumptions that i made:
1) coordinates for center of mass for multiple objects are independent of each other (ie, Xcm does not depend on Y coordinates of objects)
2) resulting center of mass for several objects is: Xcm= sum(Xi*Mi)/sum(Mi) , where Xi is X coordinate of i-th object, and Mi is that objects mass
3) same goes for Ycm, and Zcm is not even needed here
4) Xi*Mi is in 1E10 range, sum(Xi*Mi) is in 1E13 range
5) mass of each block 'equals' square of radius R (3rd param in input line)
6) check if center of mass (Xcm,Ycm) lies on block (Xi,Yi,Ri) is: if (sqr(Xcm-Xi)+sqr(Ycm-Yi)>= sqr(Ri)-EPS then 'unfeasible'

Basic assumptions about problem:
1) when each new k-th block is added, we need to check if every substack (i) starting from top has center of mass that lies on top of block (i-1) under it
2) So if we add k=4th block, we need to check if 4 lies on 3, if 3+4 lies on 2, if 2+3+4 lies on 1 etc


With above asumptions i made fairly simple program that keeps getting WA. After that i made 3 versions of solution, original one that used real extended type, and two integer ones, one that used int64 for sums and BigInt for square/radius check, and other who use BigInt for all calculations.

Since I'm still getting WA, I wonder if some of my assumptions are wrong, or if there is some special input case that i'm not covering

can anyone help me ? why i'm getting WA ?

Try the following testcase:
2
0 0 10
9 9 10

Shoud output:
Unfeasible 1

center of mass of block 1 is ( x=9 , y=9 ) which is on the surface of
block 0 , Could you tell me why is it unfeasible ?

The point (9,9) is not inside a circle of radius 10, which means the top block's centre of mass does not rest on the bottom block.

Thanks elif and stubbscroll !
I got AC

Hello. My algorithm is as following:
I'm getting wrong answer. What's wrong with this algorithm?

Is this output correct?
Input Output (This output is wrong) Edit: Corrected the input, as Jan said.

Thanks.

Your case is wrong. However, try the case...

Input: Output: Hope it helps.

Hello Jan. Thanks for your answer.

Can you clarify me why is the correct output 4?

Here's my reasoning:

(I only consider x,y coordinates)

Block 0 is placed in the ground at point (10000, 10000).

Block 1 is placed over block 0 at point (9999, 10000), 1 unit away from block 0's center.

Block 2 is placed over block 1 at point (9998, 10000), 2 units away from block 0's center and 1 unit away from block 1's center.

Block 3 is placed over block 2 at point (9997, 10000), but it is exactly 3 units away from block 0's center, which makes the tower unstable and "Unfeasible 3".

What's wrong with this approach?

Thanks a lot!

I don't understand how did you take your decision. I am describing the basic theory...

If some objects(say y1, y2, ..., yn) are placed over another object (say X) then the center of masses of y1, y2, ..., yn must be inside the body of X. Otherwise the objects (y1, y2, ..., yn) will fall.

Now if we generalize the theory a bit..

Say y1, y2, y3, ..., yn are placed. Now if we want to place ym (m=n+1), then the following decisions can be made..

1) The center of mass of ym must be inside of yn.
2) The center of masses of ym, yn must be inside of y(n-1).
3) The center of masses of ym, yn, y(n-1) must be inside of y(n-2).
...
n) The center of masses of ym, yn, ..., y2 must be inside of y1.

This way we can find whether a design is feasible. Hope it helps.

Thanks Jan.

My algorithm was wrong, I was not considering the center of mass of all the discs above a given disc but only the disc immediately on it.

Thanks to your clarification I could get accepted after some wrong answer due to a precision error. I used const double EPS = 10E-9 for the comparisons and it worked.

Any way, here's some extra input/output:

Input Output: Thanks Jan!