Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <map>
- #include <string>
- typedef std::map<std::string, double> point_t; // point is (point["x"], point["y"])
- class segment_t : public std::pair<point_t, point_t> {
- public:
- segment_t() {
- std::cin >> this->first["x"] >> this->first["y"] >> this->second["x"] >> this->second["y"];
- }
- };
- typedef std::map<std::string, double> equation_t; // equation id (eq["k"] * x + eq["b"] = y)
- using std::max;
- using std::min;
- equation_t equation(segment_t seg);
- point_t intersection(equation_t eq1, equation_t eq2);
- bool intersect(segment_t seg1, segment_t seg2);
- bool at(point_t point, segment_t seg);
- std::pair<bool, bool> exeption(segment_t seg1, segment_t seg2);
- int main() {
- std::cout << ((intersect(segment_t(), segment_t())) ? "YES" : "NO");
- }
- equation_t equation(segment_t seg) {
- // returns equation of segment seg.
- // WARNING: x1 must be not equal x2
- equation_t result;
- result["k"] =(seg.second["y"] - seg.first["y"]) / (seg.second["x"] - seg.first["x"]);
- result["b"] = seg.first["y"] - seg.first["x"] * result["k"];
- return result;
- }
- point_t intersection(equation_t eq1, equation_t eq2) {
- // returns intersection of straigts, whose equations're eq1 and eq2
- // WARNING: k1 must be not equal k2
- point_t result;
- result["x"] = (eq2["b"] - eq1["b"]) / (eq1["k"] - eq2["k"]);
- result["y"] = result["x"] * eq1["k"] + eq1["b"];
- return result;
- }
- bool intersect(segment_t seg1, segment_t seg2) {
- std::pair<bool, bool> exept = exeption(seg1, seg2);
- if (exept.first) return exept.second;
- equation_t eq1, eq2;
- eq1 = equation(seg1);
- eq2 = equation(seg2);
- if (eq1["k"] == eq2["k"]) {
- if (eq1["b"] != eq2["b"]) return false;
- if (max(seg1.first["x"], seg2.second["x"]) < min(seg2.first["x"], seg2.second["x"]))
- return false;
- if (max(seg2.first["x"], seg2.second["x"]) < min(seg1.first["x"], seg1.second["x"]))
- return false;
- return true;
- }
- point_t intersec = intersection(eq1, eq2);
- return (at(intersec, seg1) && at(intersec, seg2));
- }
- bool at(point_t point, segment_t seg) {
- // returns true if point belongs to seg
- if (point["x"] > max(seg.first["x"], seg.second["x"])) return false;
- if (point["x"] < min(seg.first["x"], seg.second["x"])) return false;
- if (point["y"] > max(seg.first["y"], seg.second["y"])) return false;
- if (point["y"] < min(seg.first["y"], seg.second["y"])) return false;
- return true;
- }
- std::pair<bool, bool> exeption(segment_t seg1, segment_t seg2) {
- std::pair<bool, bool> result;
- if ((seg1.first["x"] != seg1.second["x"]) && (seg2.first["x"] != seg2.second["x"])) {
- result.first = false;
- result.second = false;
- return result;
- }
- if (seg2.first["x"] == seg2.second["x"]) {
- if (seg1.first["x"] != seg1.second["x"]) return exeption(seg2, seg1);
- result.first = true;
- if (seg1.first["x"] != seg2.first["x"]) {
- result.second = false;
- return result;
- }
- if (max(seg1.first["y"], seg2.second["y"]) < min(seg2.first["y"], seg2.second["y"])) {
- result.second = false;
- return result;
- }
- if (max(seg2.first["y"], seg2.second["y"]) < min(seg1.first["y"], seg1.second["y"])) {
- result.second = false;
- return result;
- }
- result.second = true;
- return result;
- }
- equation_t eq = equation(seg2);
- point_t intersec;
- intersec["x"] = seg1.first["x"];
- intersec["y"] = seg1.first["x"] * eq["k"] + eq["b"];
- result.first = true;
- result.second = at(intersec, seg1);
- return result;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement