Advertisement
Guest User

Untitled

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