Хоёр хэрчим огтлолцож байгааг шалгах¶

Танд $(a, b)$ ба $(c, d)$ гэсэн хоёр хэрчим өгөгдсөн. Та тэдгээр огтлолцож байгаа эсэхийг шалгах ёстой. Мэдээж та тэдгээрийн огтлолцлыг олж, хоосон биш эсэхийг шалгаж болно, гэвч бүхэл тоон координаттай хэрчмүүдийн хувьд үүнийг бүхэл тоогоор хийж болохгүй. Энд тайлбарласан арга нь бүхэл тоогоор ажиллаж чадна.

Алгоритм¶

Эхлээд хэрчмүүд нэг шулууны хэсэг байх тохиолдлыг авч үзье. Энэ тохиолдолд тэдгээрийн $Ox$ ба $Oy$ дээрх проекцууд огтлолцож байгаа эсэхийг шалгахад хангалттай. Өөр тохиолдолд $a$ ба $b$ нь $(c, d)$ шулууны нэг талд орших ёсгүй, мөн $c$ ба $d$ нь $(a, b)$ шулууны нэг талд орших ёсгүй. Үүнийг хэдэн вектор үржвэрээр шалгаж болно.

Implementation¶

The given algorithm is implemented for integer points. Of course, it can be easily modified to work with doubles.

struct pt {
    long long x, y;
    pt() {}
    pt(long long _x, long long _y) : x(_x), y(_y) {}
    pt operator-(const pt& p) const { return pt(x - p.x, y - p.y); }
    long long cross(const pt& p) const { return x * p.y - y * p.x; }
    long long cross(const pt& a, const pt& b) const { return (a - *this).cross(b - *this); }
};

int sgn(const long long& x) { return x >= 0 ? x ? 1 : 0 : -1; }

bool inter1(long long a, long long b, long long c, long long d) {
    if (a > b)
        swap(a, b);
    if (c > d)
        swap(c, d);
    return max(a, c) <= min(b, d);
}

bool check_inter(const pt& a, const pt& b, const pt& c, const pt& d) {
    if (c.cross(a, d) == 0 && c.cross(b, d) == 0)
        return inter1(a.x, b.x, c.x, d.x) && inter1(a.y, b.y, c.y, d.y);
    return sgn(a.cross(b, c)) != sgn(a.cross(b, d)) &&
           sgn(c.cross(d, a)) != sgn(c.cross(d, b));
}