anonymous
  • anonymous
Hannibal is on a mission. He has to shoot a criminal. Hannibal was on the point (0, 0) and the criminal is on the point (Xc, Yc). But there is a wall between the point (X1, Y1) and (X2, Y2). You have to tell whether Hannibal can shoot criminal or not. INPUT: First line contains the total number of test cases T. For each test case, a single line contains space separated integers denoting X1, Y1, X2, Y2, Xc, Yc. OUTPUT: For each test case display YES, if Hannibal can shoot the criminal. Otherwise, display NO. Constraints: 1 <= T <= 100 1 <= X, Y <= 1000000 Sample Input
Computer Science
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
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.
katieb
  • katieb
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
anonymous
  • anonymous
@Algorithmic
Lyrae
  • Lyrae
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 )
Lyrae
  • Lyrae
Yes, you calculate y=mx+b for the bullet path and the wall.

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

anonymous
  • anonymous
can you write the code in C or C++ ? @Lyrae @AngusV
Lyrae
  • Lyrae
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.
anonymous
  • anonymous
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.
1 Attachment
Lyrae
  • Lyrae
We are here to untangle problems, guide and explain, not to write your code!
anonymous
  • anonymous
AugusV told me himself
Lyrae
  • Lyrae
Try to write the code your self. If you run in to trouble post it here and we'll do our best help.
anonymous
  • anonymous
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|
anonymous
  • anonymous
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;
anonymous
  • anonymous
@Archit910
anonymous
  • anonymous
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.
anonymous
  • anonymous
Nothing that we can't conquer with some brute force though. There are four cases to discuss: if (X1Y2) if (X1X2&&Y1X2&&Y1>Y2) if (X2
anonymous
  • anonymous
yeah,thanks a lot :)
anonymous
  • anonymous
Final code: #include int main() { int T; printf ("\n Input the number of test cases:"); scanf ("%d", &T); int counter; int X1,X2,Y1,Y2,Xc,Yc,a_bp,b_bp,a_wall,b_wall,Xp,Yp; // Declarations for (counter=0;counter<=T;counter++) printf("\n X1="); scanf("%d",&X1); printf("\n X2="); scanf("%d",&X2); printf("\n Y1="); scanf("%d",&Y1); printf("\n Y2="); scanf("%d",&Y2); printf("\n Xc="); scanf("%d",&Xc); printf("\n Yc="); scanf("%d",&Yc); // Bullet path a_bp=(Xc-0)/(Yc-0); b_bp=0-a_bp*Xc; // Wall path a_wall=(Y2-Y1)/(X2-X1); b_wall=Y1-a_wall*X1; // 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 if (a_bp!=a_wall) Xp=(b_wall-b_bp)/(a_bp-a_wall); Yp=a_bp*Xp+b_bp; // And then we check if that point is on the wall itself if (X1Y2) if (X1X2&&Y1X2&&Y1>Y2) if (X2
anonymous
  • anonymous
it is not working
anonymous
  • anonymous
What is the issue ? It works just fine here.
anonymous
  • anonymous
it say stdin is empty
anonymous
  • anonymous
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
anonymous
  • anonymous
I don't have a clue. It works just fine here.
1 Attachment
anonymous
  • anonymous
1 Attachment
anonymous
  • anonymous
What is that ?

Looking for something else?

Not the answer you are looking for? Search for more explanations.