Advertisement
Guest User

Untitled

a guest
Oct 31st, 2014
145
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.78 KB | None | 0 0
  1. #include <iostream>
  2. #include <map>
  3. #include <string>
  4.  
  5. typedef std::map<std::string, double> point_t;  // point is (point["x"], point["y"])
  6. typedef std::pair<point_t, point_t> segment_t;
  7. typedef std::map<std::string, double> equation_t;  // equation id (eq["k"] * x + eq["b"] = y)
  8.  
  9. using std::max;
  10. using std::min;
  11.  
  12. equation_t equation(segment_t seg);
  13. point_t intersection(equation_t eq1, equation_t eq2);
  14. bool intersect(segment_t seg1, segment_t seg2);
  15. bool at(point_t point, segment_t seg);
  16. std::pair<bool, bool> exeption(segment_t seg1, segment_t seg2);
  17.  
  18. int main() {
  19.     segment_t seg1, seg2;
  20.     std::cin >> seg1.first["x"] >> seg1.first["y"] >> seg1.second["x"] >> seg1.second["y"];
  21.     std::cin >> seg2.first["x"] >> seg2.first["y"] >> seg2.second["x"] >> seg2.second["y"];
  22.  
  23.     std::cout << ((intersect(seg1, seg2)) ? "YES" : "NO");
  24. }
  25.  
  26. equation_t equation(segment_t seg) {
  27.     // returns equation of segment seg.
  28.     // WARNING: x1 must be not equal x2
  29.  
  30.     equation_t result;
  31.     result["k"] =(seg.second["y"] - seg.first["y"]) / (seg.second["x"] - seg.first["x"]);
  32.     result["b"] = seg.first["y"] - seg.first["x"] * result["k"];
  33.     return result;
  34. }
  35.  
  36. point_t intersection(equation_t eq1, equation_t eq2) {
  37.     // returns intersection of straigts, whose equations're eq1 and eq2
  38.     // WARNING: k1 must be not equal k2
  39.  
  40.     point_t result;
  41.     result["x"] = (eq2["b"] - eq1["b"]) / (eq1["k"] - eq2["k"]);
  42.     result["y"] = result["x"] * eq1["k"] + eq1["b"];
  43.     return result;
  44. }
  45.  
  46. bool intersect(segment_t seg1, segment_t seg2) {
  47.     std::pair<bool, bool> exept = exeption(seg1, seg2);
  48.     if (exept.first) return exept.second;
  49.  
  50.     equation_t eq1, eq2;
  51.     eq1 = equation(seg1);
  52.     eq2 = equation(seg2);
  53.     if (eq1["k"] == eq2["k"]) {
  54.         if (eq1["b"] != eq2["b"]) return false;
  55.  
  56.         if (max(seg1.first["x"], seg2.second["x"]) < min(seg2.first["x"], seg2.second["x"]))
  57.             return false;
  58.         if (max(seg2.first["x"], seg2.second["x"]) < min(seg1.first["x"], seg1.second["x"]))
  59.             return false;
  60.         return true;
  61.     }
  62.  
  63.     point_t intersec = intersection(eq1, eq2);
  64.     return (at(intersec, seg1) && at(intersec, seg2));
  65. }
  66.  
  67. bool at(point_t point, segment_t seg) {
  68.     // returns true if point belongs to seg
  69.  
  70.     if (point["x"] > max(seg.first["x"], seg.second["x"])) return false;
  71.     if (point["x"] < min(seg.first["x"], seg.second["x"])) return false;
  72.     if (point["y"] > max(seg.first["y"], seg.second["y"])) return false;
  73.     if (point["y"] < min(seg.first["y"], seg.second["y"])) return false;
  74.     return true;
  75. }
  76.  
  77. std::pair<bool, bool> exeption(segment_t seg1, segment_t seg2) {
  78.     std::pair<bool, bool> result;
  79.     if ((seg1.first["x"] != seg1.second["x"]) && (seg2.first["x"] != seg2.second["x"])) {
  80.         result.first = false;
  81.         result.second = false;
  82.         return result;
  83.     }
  84.  
  85.     if (seg2.first["x"] == seg2.second["x"]) {
  86.         if (seg1.first["x"] != seg1.second["x"]) return exeption(seg2, seg1);
  87.  
  88.         result.first = true;
  89.  
  90.         if (seg1.first["x"] != seg2.first["x"]) {
  91.             result.second = false;
  92.             return result;
  93.         }
  94.  
  95.         if (max(seg1.first["y"], seg2.second["y"]) < min(seg2.first["y"], seg2.second["y"])) {
  96.             result.second = false;
  97.             return result;
  98.         }
  99.         if (max(seg2.first["y"], seg2.second["y"]) < min(seg1.first["y"], seg1.second["y"])) {
  100.             result.second = false;
  101.             return result;
  102.         }
  103.         result.second = true;
  104.         return result;
  105.     }
  106.  
  107.     equation_t eq = equation(seg2);
  108.     point_t intersec;
  109.     intersec["x"] = seg1.first["x"];
  110.     intersec["y"] = seg1.first["x"] * eq["k"] + eq["b"];
  111.     result.first = true;
  112.     result.second = at(intersec, seg1);
  113.     return result;
  114. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement