At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
Hanibal can shoot the criminal: |dw:1434191219837:dw| Hanibal cannot shoot the criminal: |dw:1434191688599:dw| There are several approaches to this; two of them are: 1. You the treat wall and bullet path as lines (calculate mx+b) and see if they intersect on the given intervals. 2. You treat wall and bullet path as line segments and use linear algebra find whether they intersect or not. This one is a bit tricky but a lot of resources are available on the web (i.e. http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect )
Yes, you calculate y=mx+b for the bullet path and the wall.
can you write the code in C or C++ ? @Lyrae @AngusV
You have to check if the lines intersect. A very simple (but far from optimal) method is to iterate over the domain of the bullet path, in each iteration calculate y for both lines, the lines intersect if the ys are equal.
Let me add this. Don't mind the romanian words, they're not important. I wrote this for a different thing a while back. What this basically shows is the "fast way" of figuring out the equation of a line by knowing the coordinates of two points (A and B). The equation of a line is ax+b and here you get the direct formula for a and b considering coordinates only.
We are here to untangle problems, guide and explain, not to write your code!
AugusV told me himself
Try to write the code your self. If you run in to trouble post it here and we'll do our best help.
So at the start of your program the first thing you want to do is figure out the equation of the two lines you wish to compute. For the bullet path: a_bp=(Xc-0)/(Yc-0); b_bp=0-a*Xc; // The equation is a_bp*x+b_bp For the wall it's: a_wall=(Y2-Y1)/(X2-X1); b_wall=Y1-a_wall*X1; // The equation is a_wall*x+b_wall There are two very important things we need to check for. 1) Do the paths interesect at all. That is pretty simple if you consider that all we need to do is to check if the two lines are parallel or not. If they are not parallel they will cross each other at some points (at least in Euclidian space). If you recall. there's a neat trick that you can use when you have the equation of two lines and that is: - if the slopes of those two lines are equal then the lines are parallel This is a best case scenario where the answer is right there in front of you. We check if the slopes are equal but let me add in a little exceptions; if (a_bp==a_wall && b_bp!=b_wall) printf ("YES"); Because if the two lines are paralel he can shoot the criminal without a problem ONLY if the equation of the wall is not identical to the equation of the tragectory (hence why I added the "&& b_bp!=b_wall" condition). Here's what could happen if you didn't add that condition: |dw:1434195689105:dw|
if (a_bp==a_wall && b_bp!=b_wall) printf ("YES"); if (a_bp==a_wall && b_bp==b_wall) printf ("NO"); Of course, it is likely that the two slopes (a_bp and a_wall) won't be equal and so we continue. Second question we pose is: 2) If the paths intersect, where do they intersect at all ? Again, very simple to put into our program if we use a little math. Suppose two paths do intersect then from math we know that there exists a point (let's call it point P) so that Xp and Yp satisfy both equations. We've already treated the case when the lines DON'T intersect at all so we know for a fact that at this stage they surely do intersect. |dw:1434196219916:dw| We have the two equations which we work out a bit to our favor. To verify both equations we must find Xp and Yp so that: a_bp*Xp+b_bp=Yp; a_wall*Xp+b_wall=Yp; Let's help our computer solve that equation a bit. You will notice how both equal Yp so therefore we can equate those two: a_bp*Xp+b_bp=a_wall*Xp+b_wall; We "flip" them over a little bit: a_bp*Xp-a_wall*Xp=b_wall-b_bp And factor a little: Xp(a_bp-a_wall)=b_wall-b_bp And we get that: Xp=(b_wall-b_bp)/(a_bp-a_wall) You can get Yp out of any of those two equations, so let's just go for the first one: Yp=a_bp*Xp+b_bp. And these are the two things you have to write in your code: Xp=(b_wall-b_bp)/(a_bp-a_wall); Yp=a_bp*Xp+b_bp;
Great, now we have the coordinates of our point of intersection. Final question we pose is: 3) Is this point on the wall or not ? You see, we've only treated the equation so far - not the actual wall. |dw:1434196725930:dw| To do this, we consider what conditions have to be met so that our point is on the wall itself. We already know the point is on the line that is described by the equation of the wall so that shouldn't be so hard to do. I'm going to go for the "straight forward" way of doing this. Some problems may arise here due to how the person chooses order of inputs and notations. Here's what I mean: |dw:1434197211604:dw| Easy, right ? But here's the catch. Suppose you have this scenario |dw:1434197416425:dw| Spices up things a little.
Nothing that we can't conquer with some brute force though. There are four cases to discuss: if (X1
if (X1 X2&&Y1 X2&&Y1>Y2)
yeah,thanks a lot :)
Final code: #include
printf ("\n Input the number of test cases:");
scanf ("%d", &T);
// Bullet path
// Wall path
// Checks if paths are parallel and/or identical
if (a_bp==a_wall && b_bp!=b_wall) printf ("YES");
if (a_bp==a_wall && b_bp==b_wall) printf ("NO");
// And if they're not we find the coordinates of the point of intersection
// And then we check if that point is on the wall itself
if (X1 Y2)
if (X1 X2&&Y1 X2&&Y1>Y2)
it is not working
What is the issue ? It works just fine here.
it say stdin is empty
Sample Input(Plaintext Link) 2 1 1 2 2 3 3 2 2 3 3 1 1 Sample Output(Plaintext Link) NO YES this should be the i/o i/p
What is that ?