I know an idea how to solve it, but I need to rotate a vector in a definite plane.
I'm no so good in 3D-geometry yet, so I would appreciate any advice how to do it efficiently.
Maybe someone could give me a link to an appropriate article...

Edited by author 03.05.2009 22:12

This was very simple problem for me because I could find
1. formula for distance in 3D from point to line
2. formula for rotation matrix with given line.
All information in Wicpedia articles.
3. formula for projection point to line in 3D -at the same place.
Also I known cosine theorem in advance.

"No solution" I proved in __int64 manner and was right.

But problem about Ostap I can not to solve. This is potential theory problem and I try to use union-find methods but unsuccessfully.

Edited by author 25.05.2009 11:47

I've found simplier solution, which calculates the coordinates of required point in 2D, then just changes the basis.

Now about Ostap)) I've used an algo based on disjoint sets.
For every workman I store the difference between his and his ancestor wages.
And for every set I store the minimum such difference to check conditions efficiently.