Vision problem
https://www.codechef.com/JUNE18B/problems/VSN
can anyone provide a hint for this problem?
You are given two points P and Q and an opaque sphere in a three-dimensional space. The point P is not moving, while Q is moving in a straight line with constant velocity. You are also given a direction vector d with the following meaning: the position of Q at time t is Q(t)=Q(0)+d⋅t, where Q(0) is the initial position of Q.
It is guaranteed that Q is not visible from P initially (at time t=0). It is also guaranteed that P and Q do not touch the sphere at any time.
Find the smallest positive time tv when Q is visible from P, i.e. when the line segment connecting points P and Q does not intersect the sphere.
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains 13 space-separated integers.
The first three integers Px,Py,Pz denote the coordinates of P.
The next three integers Qx,Qy,Qz denote the initial coordinates of Q.
The next three integers dx,dy,dz denote the components of the direction vector d.
The last four integers cx,cy,cz,r denote the coordinates of the centre of the sphere and its radius.
Output
For each test case, print a single line containing one real number — the time tv. Your answer will be considered correct if its absolute or relative error does not exceed 10−6. It is guaranteed that tv exists and does not exceed 109.
Constraints
1≤T≤105
the absolute values of coordinates of all points do not exceed 2⋅109
1≤r≤109
Subtasks
Subtask #1 (25 points): Pz=Qz=dz=cz=0
Subtask #2 (75 points): original constraints
Example Input
1
3 0 0 -10 -10 0 0 10 0 0 -3 0 3
Example Output
1.0000000000
can anyone provide a hint for this problem?
You are given two points P and Q and an opaque sphere in a three-dimensional space. The point P is not moving, while Q is moving in a straight line with constant velocity. You are also given a direction vector d with the following meaning: the position of Q at time t is Q(t)=Q(0)+d⋅t, where Q(0) is the initial position of Q.
It is guaranteed that Q is not visible from P initially (at time t=0). It is also guaranteed that P and Q do not touch the sphere at any time.
Find the smallest positive time tv when Q is visible from P, i.e. when the line segment connecting points P and Q does not intersect the sphere.
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains 13 space-separated integers.
The first three integers Px,Py,Pz denote the coordinates of P.
The next three integers Qx,Qy,Qz denote the initial coordinates of Q.
The next three integers dx,dy,dz denote the components of the direction vector d.
The last four integers cx,cy,cz,r denote the coordinates of the centre of the sphere and its radius.
Output
For each test case, print a single line containing one real number — the time tv. Your answer will be considered correct if its absolute or relative error does not exceed 10−6. It is guaranteed that tv exists and does not exceed 109.
Constraints
1≤T≤105
the absolute values of coordinates of all points do not exceed 2⋅109
1≤r≤109
Subtasks
Subtask #1 (25 points): Pz=Qz=dz=cz=0
Subtask #2 (75 points): original constraints
Example Input
1
3 0 0 -10 -10 0 0 10 0 0 -3 0 3
Example Output
1.0000000000
Last edited on
@lastchance how the hell you do this level of prgramming.You are awesome bro.Can you help us to code like you?What should we practice?
These questions test your ability to understand a problem. Once you understand the problem, it's much simpler.
Here's the same problem.
I'll tell you two points in 3D space. One of them is moving. I'll tell you which way it's moving, and how fast. Your job is to tell me when you can draw a straight line between them. You can't draw a straight line between them at the start, because there's a big circle in the way; I'll tell you about the circle, how big it is.
When the moving point comes out from behind the circle, then you can draw the straight line between them. Tell me what time it comes out from behind the circle.
One way to solve this would be to write a function that tells you if you can draw a straight line between two points (i.e. without crossing the circle), given the location of the circle. Then, move the location of the moving point until you can draw that straight line. Use iteratative movements, back and forth, to get more accuracy.
There is another way to do, without iteration; the exact point can be found by calculation and line projection. See if you can figure it out. On paper. With a pencil and sketching.
Everyone has their own way of learning how to solve problems like this, but this problem isn't so much a programming task as a thinking task. This is mathematics and geometry and understanding lines and intersections. The fact that the answer will be programmed isn't irrelevant, but that's really not the difficult part. The difficulty is in thinking about it.
Here's the same problem.
I'll tell you two points in 3D space. One of them is moving. I'll tell you which way it's moving, and how fast. Your job is to tell me when you can draw a straight line between them. You can't draw a straight line between them at the start, because there's a big circle in the way; I'll tell you about the circle, how big it is.
When the moving point comes out from behind the circle, then you can draw the straight line between them. Tell me what time it comes out from behind the circle.
One way to solve this would be to write a function that tells you if you can draw a straight line between two points (i.e. without crossing the circle), given the location of the circle. Then, move the location of the moving point until you can draw that straight line. Use iteratative movements, back and forth, to get more accuracy.
There is another way to do, without iteration; the exact point can be found by calculation and line projection. See if you can figure it out. On paper. With a pencil and sketching.
Everyone has their own way of learning how to solve problems like this, but this problem isn't so much a programming task as a thinking task. This is mathematics and geometry and understanding lines and intersections. The fact that the answer will be programmed isn't irrelevant, but that's really not the difficult part. The difficulty is in thinking about it.
Last edited on
t = (-b +- sqrt( b2-4ac ) ) / ( 2a)
or, if a is 0 (as in their example),
t = -c/b
But YOU have to work out what a, b, c are!
Draw it. Maybe do a little bit of vector analysis and/or geometry.
or, if a is 0 (as in their example),
t = -c/b
But YOU have to work out what a, b, c are!
Draw it. Maybe do a little bit of vector analysis and/or geometry.
Last edited on
Has anybody found out what "a","b" and "c" are?
If yes,then please share them here!!
If yes,then please share them here!!
@the1marvellous No one will provide you with code on the plate. This is the "almost solution" of the question. All you got to do is some Algebra.
Can anyone help me to find out the problem in my code....During submission, my code pased one tast case of subtask1...
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
ll t;
cin>>t;
while(t--)
{
ll p[14];
for(ll i=0;i<13;i++)
{
cin>>p[i];
}
ll x1=p[0],y1=p[1],z1=p[2],x2=p[3],y2=p[4],z2=p[5],dx=p[6],dy=p[7],dz=p[8],x3=p[9],y3=p[10],z3=p[11],r=p[12];
ll a,b,c,d,e,x,y,z;
a=(x2-x1)*(y3-y1)-(y2-y1)*(x3-x1);
b=(x1-x3)*dy-(y1-y3)*dx;
c=r*r*((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
d=dx*dx*r*r+dy*dy*r*r;
e=r*r*(2*(x2-x1)*dx+2*(y2-y1)*dy);
//cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<e<<endl;
x=b*b-d;
y=2*a*b-e;
z=a*a-c;
//cout<<x<<" "<<y<<" "<<z<<endl;
double D,D1,D2,E;
D=(double)sqrt(y*y-4*x*z);
//cout<<D<<endl;
if(x==0)
{
D1=double(-z/y);
D2=D1;
}
else
{
D1=double(y-D)/(2*x);
D2=double(y+D)/(2*x);
}
if(D1<=D2)
{
if(D1>=0)
E=D1;
else
E=D2;
}
else
{
if(D2>=0)
E=D2;
else
E=D1;
}
if(E<0)
E=-E;
cout<<E<<endl;
}
}
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
ll t;
cin>>t;
while(t--)
{
ll p[14];
for(ll i=0;i<13;i++)
{
cin>>p[i];
}
ll x1=p[0],y1=p[1],z1=p[2],x2=p[3],y2=p[4],z2=p[5],dx=p[6],dy=p[7],dz=p[8],x3=p[9],y3=p[10],z3=p[11],r=p[12];
ll a,b,c,d,e,x,y,z;
a=(x2-x1)*(y3-y1)-(y2-y1)*(x3-x1);
b=(x1-x3)*dy-(y1-y3)*dx;
c=r*r*((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
d=dx*dx*r*r+dy*dy*r*r;
e=r*r*(2*(x2-x1)*dx+2*(y2-y1)*dy);
//cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<e<<endl;
x=b*b-d;
y=2*a*b-e;
z=a*a-c;
//cout<<x<<" "<<y<<" "<<z<<endl;
double D,D1,D2,E;
D=(double)sqrt(y*y-4*x*z);
//cout<<D<<endl;
if(x==0)
{
D1=double(-z/y);
D2=D1;
}
else
{
D1=double(y-D)/(2*x);
D2=double(y+D)/(2*x);
}
if(D1<=D2)
{
if(D1>=0)
E=D1;
else
E=D2;
}
else
{
if(D2>=0)
E=D2;
else
E=D1;
}
if(E<0)
E=-E;
cout<<E<<endl;
}
}
Hey.
Can someone just help me with the equation of the line. I just want to know that is it coming in the form of t^2 which means we'll finally get an equation of t^4 to solve onto?
Can someone just help me with the equation of the line. I just want to know that is it coming in the form of t^2 which means we'll finally get an equation of t^4 to solve onto?
I can help anyone with 1st 4 codes but in turn you must send me any code after VSN problem
Topic archived. No new replies allowed.