A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 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

  • This Question is Closed
  1. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @Algorithmic

  2. Lyrae
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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 )

  3. Lyrae
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Yes, you calculate y=mx+b for the bullet path and the wall.

  4. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    can you write the code in C or C++ ? @Lyrae @AngusV

  5. Lyrae
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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.

  6. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
  7. Lyrae
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    We are here to untangle problems, guide and explain, not to write your code!

  8. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    AugusV told me himself

  9. Lyrae
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Try to write the code your self. If you run in to trouble post it here and we'll do our best help.

  10. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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|

  11. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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;

  12. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @Archit910

  13. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

  14. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Nothing 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.

  15. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    yeah,thanks a lot :)

  16. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Final 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=(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 (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"); }

  17. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    it is not working

  18. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    What is the issue ? It works just fine here.

  19. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    it say stdin is empty

  20. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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

  21. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I don't have a clue. It works just fine here.

    1 Attachment
  22. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    1 Attachment
  23. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    What is that ?

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

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

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
  • 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.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.