Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <map>
- typedef std::map<std::string, long long int> point_t;
- bool intersect(point_t a, point_t b, point_t c, point_t d);
- bool proj_intersec(long long int p11, long long int p12, long long int p21, long long int p22);
- long long int det(point_t a, point_t b, point_t c);
- int main() {
- point_t a, b, c, d; // pending segments are [a, b] and [c, d]
- std::cin >> a["x"] >> a["y"] >> b["x"] >> b["y"];
- std::cin >> c["x"] >> c["y"] >> d["x"] >> d["y"];
- std::cout << ((intersect(a, b, c, d)) ? "YES" : "NO");
- return 0;
- }
- bool intersect(point_t a, point_t b, point_t c, point_t d) {
- // returns true if segments [a, b], [c, d] intersect
- return proj_intersec(a["x"], b["x"], c["x"], d["x"]) && // checking that projects
- proj_intersec(a["y"], b["y"], c["y"], d["y"]) && // on axises are intersecting
- (det(a, b, c) * det(a, b, d) <= 0) && // checking that segments lie
- (det(c, d, a) * det(c, d, b) <= 0); // in different half-planes
- }
- bool proj_intersec(long long int p11, long long int p12, long long int p21, long long int p22) {
- // returns true if segments [p11, p12] and [p21, p22] intersect
- if (p11 > p12) std::swap(p11, p12);
- if (p21 > p22) std::swap(p21, p22);
- return std::max(p11, p21) <= std::min(p12, p22);
- }
- long long int det(point_t a, point_t b, point_t c) {
- // returns oriented area of triangle with vertices a, b, c
- return (b["x"] - a["x"]) * (c["y"] - a["y"]) -
- (b["y"] - a["y"]) * (c["x"] - a["x"]);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement