A community for students.
Here's the question you clicked on:
 0 viewing
anonymous
 one year ago
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
anonymous
 one year ago
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

This Question is Closed

Lyrae
 one year ago
Best ResponseYou've already chosen the best response.1Hanibal 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/howdoyoudetectwheretwolinesegmentsintersect )

Lyrae
 one year ago
Best ResponseYou've already chosen the best response.1Yes, you calculate y=mx+b for the bullet path and the wall.

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0can you write the code in C or C++ ? @Lyrae @AngusV

Lyrae
 one year ago
Best ResponseYou've already chosen the best response.1You 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
 one year ago
Best ResponseYou've already chosen the best response.0Let 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.

Lyrae
 one year ago
Best ResponseYou've already chosen the best response.1We are here to untangle problems, guide and explain, not to write your code!

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0AugusV told me himself

Lyrae
 one year ago
Best ResponseYou've already chosen the best response.1Try to write the code your self. If you run in to trouble post it here and we'll do our best help.

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0So 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=(Xc0)/(Yc0); b_bp=0a*Xc; // The equation is a_bp*x+b_bp For the wall it's: a_wall=(Y2Y1)/(X2X1); b_wall=Y1a_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
 one year ago
Best ResponseYou've already chosen the best response.0if (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*Xpa_wall*Xp=b_wallb_bp And factor a little: Xp(a_bpa_wall)=b_wallb_bp And we get that: Xp=(b_wallb_bp)/(a_bpa_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_wallb_bp)/(a_bpa_wall); Yp=a_bp*Xp+b_bp;

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Great, 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
 one year ago
Best ResponseYou've already chosen the best response.0Nothing that we can't conquer with some brute force though. There are four cases to discuss: if (X1<X2&&Y1<Y2) if (X1<Xp && Xp<X2 && Y1<Yp && Yp<Y2) printf ("YES"); else printf ("NO"); if (X1<X2&&Y1>Y2) if (X1<Xp && Xp<X2 && Y2<Yp && Yp<Y1) printf ("YES"); else printf ("NO"); if (X1>X2&&Y1<Y2) if (X2<Xp && Xp<X1 && Y1<Yp && Yp<Y2) printf ("YES"); else printf ("NO"); if (X1>X2&&Y1>Y2) if (X2<Xp && Xp<X1 && Y2<Yp && Yp<Y1) printf ("YES"); else printf ("NO"); That should cover it. I hope there aren't any exceptions I've overlooked.

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0yeah,thanks a lot :)

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Final code: #include <stdio.h> 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=(Xc0)/(Yc0); b_bp=0a_bp*Xc; // Wall path a_wall=(Y2Y1)/(X2X1); b_wall=Y1a_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_wallb_bp)/(a_bpa_wall); Yp=a_bp*Xp+b_bp; // And then we check if that point is on the wall itself if (X1<X2&&Y1<Y2) if (X1<Xp && Xp<X2 && Y1<Yp && Yp<Y2) printf ("YES"); else printf ("NO"); if (X1<X2&&Y1>Y2) if (X1<Xp && Xp<X2 && Y2<Yp && Yp<Y1) printf ("YES"); else printf ("NO"); if (X1>X2&&Y1<Y2) if (X2<Xp && Xp<X1 && Y1<Yp && Yp<Y2) printf ("YES"); else printf ("NO"); if (X1>X2&&Y1>Y2) if (X2<Xp && Xp<X1 && Y2<Yp && Yp<Y1) printf ("YES"); else printf ("NO"); }

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0What is the issue ? It works just fine here.

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0it say stdin is empty

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Sample 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
 one year ago
Best ResponseYou've already chosen the best response.0I don't have a clue. It works just fine here.
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.