Advertisement
Guest User

Untitled

a guest
Oct 31st, 2014
141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.54 KB | None | 0 0
  1. #include <iostream>
  2. #include <map>
  3.  
  4. typedef std::map<std::string, long long int> point_t;
  5.  
  6. bool intersect(point_t a, point_t b, point_t c, point_t d);
  7. bool proj_intersec(long long int p11, long long int p12, long long int p21, long long int p22);
  8. long long int det(point_t a, point_t b, point_t c);
  9.  
  10. int main() {
  11.     point_t a, b, c, d;  // pending segments are [a, b] and [c, d]
  12.     std::cin >> a["x"] >> a["y"] >> b["x"] >> b["y"];
  13.     std::cin >> c["x"] >> c["y"] >> d["x"] >> d["y"];
  14.  
  15.     std::cout << ((intersect(a, b, c, d)) ? "YES" : "NO");
  16.     return 0;
  17. }
  18.  
  19. bool intersect(point_t a, point_t b, point_t c, point_t d) {
  20.     // returns true if segments [a, b], [c, d] intersect
  21.     return proj_intersec(a["x"], b["x"], c["x"], d["x"]) &&  // checking that projects
  22.            proj_intersec(a["y"], b["y"], c["y"], d["y"]) &&  // on axises are intersecting
  23.            (det(a, b, c) * det(a, b, d) <= 0) &&  // checking that segments lie
  24.            (det(c, d, a) * det(c, d, b) <= 0);    // in different half-planes
  25. }
  26.  
  27. bool proj_intersec(long long int p11, long long int p12, long long int p21, long long int p22) {
  28.     // returns true if segments [p11, p12] and [p21, p22] intersect
  29.  
  30.     if (p11 > p12) std::swap(p11, p12);
  31.     if (p21 > p22) std::swap(p21, p22);
  32.     return std::max(p11, p21) <= std::min(p12, p22);
  33. }
  34.  
  35. long long int det(point_t a, point_t b, point_t c) {
  36.     // returns oriented area of triangle with vertices a, b, c
  37.     return (b["x"] - a["x"]) * (c["y"] - a["y"]) -
  38.            (b["y"] - a["y"]) * (c["x"] - a["x"]);
  39. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement