Хоёр хэрчмийн огтлолцлыг олох¶

Танд үзүүрийн цэгүүдийнх нь хосоор тодорхойлогдсон AB ба CD гэсэн хоёр хэрчим өгөгдсөн. Хэрчим бүр хэрэв үзүүрийн цэгүүд нь ижил бол ганц цэг байж болно. Та эдгээр хэрчмийн огтлолцлыг олох ёстой, энэ нь хоосон (хэрэв хэрчмүүд огтлолцохгүй бол), ганц цэг, эсвэл хэрчим (хэрэв өгөгдсөн хэрчмүүд давхцаж байвал) байж болно.

Шийдэл¶

Бид хэрчмүүдийн огтлолцлын цэгийг шулуунуудын огтлолцолтой ижил аргаар олж болно: хэрчмүүдийн үзүүрийн цэгүүдээс шулууны тэгшитгэлийг сэргээж, тэдгээр параллель эсэхийг шалгана.

Хэрэв шулуунууд параллель биш бол бид тэдгээрийн огтлолцлын цэгийг олж, тэр нь хоёр хэрчимд аль алинд нь харьяалагдах эсэхийг шалгах хэрэгтэй (үүний тулд огтлолцлын цэг X ба Y тэнхлэг дээр проекцлогдсон хэрчим бүрд харьяалагдахыг шалгахад хангалттай). Энэ тохиолдолд хариулт нь "огтлолцолгүй" эсвэл шулуунуудын огтлолцлын ганц цэг байна.

Параллель шулуунуудын тохиолдол арай илүү төвөгтэй (нэг буюу хэд хэдэн хэрчим ганц цэг байх тохиолдол ч энд хамаарна). Энэ тохиолдолд бид хоёр хэрчим нэг шулуунд харьяалагдахыг шалгах хэрэгтэй. Хэрэв харьяалагдахгүй бол хариулт нь "огтлолцолгүй". Хэрэв харьяалагдаж байвал хариулт нь нэг шулуунд харьяалагдах хэрчмүүдийн огтлолцол байх ба үүнийг хоёр хэрчмийн үзүүрийн цэгүүдийг тодорхой координатын өсөх дарааллаар эрэмбэлж, зүүн үзүүрүүдийн хамгийн баруун талынхыг, баруун үзүүрүүдийн хамгийн зүүн талынхыг авах замаар олно.

Хэрэв хоёр хэрчим хоёулаа ганц цэг бол эдгээр цэг ижил байх ёстой бөгөөд энэ шалгалтыг тусад нь хийх нь утга учиртай.

Алгоритмын эхэнд хүрээлэх хайрцгийн шалгалтыг нэмье — энэ нь хэрчмүүд нэг шулуунд харьяалагдах тохиолдолд зайлшгүй шаардлагатай бөгөөд (хөнгөн шалгалт учраас) алгоритмыг санамсаргүй тестүүд дээр дунджаар илүү хурдан ажиллуулах боломж олгоно.

Implementation¶

Here is the implementation, including all helper functions for lines and segments processing.

The main function intersect returns true if the segments have a non-empty intersection, and stores endpoints of the intersection segment in arguments left and right. If the answer is a single point, the values written to left and right will be the same.

const double EPS = 1E-9;

struct pt {
    double x, y;

    bool operator<(const pt& p) const
    {
        return x < p.x - EPS || (abs(x - p.x) < EPS && y < p.y - EPS);
    }
};

struct line {
    double a, b, c;

    line() {}
    line(pt p, pt q)
    {
        a = p.y - q.y;
        b = q.x - p.x;
        c = -a * p.x - b * p.y;
        norm();
    }

    void norm()
    {
        double z = sqrt(a * a + b * b);
        if (abs(z) > EPS)
            a /= z, b /= z, c /= z;
    }

    double dist(pt p) const { return a * p.x + b * p.y + c; }
};

double det(double a, double b, double c, double d)
{
    return a * d - b * c;
}

inline bool betw(double l, double r, double x)
{
    return min(l, r) <= x + EPS && x <= max(l, r) + EPS;
}

inline bool intersect_1d(double a, double b, double c, double d)
{
    if (a > b)
        swap(a, b);
    if (c > d)
        swap(c, d);
    return max(a, c) <= min(b, d) + EPS;
}

bool intersect(pt a, pt b, pt c, pt d, pt& left, pt& right)
{
    if (!intersect_1d(a.x, b.x, c.x, d.x) || !intersect_1d(a.y, b.y, c.y, d.y))
        return false;
    line m(a, b);
    line n(c, d);
    double zn = det(m.a, m.b, n.a, n.b);
    if (abs(zn) < EPS) {
        if (abs(m.dist(c)) > EPS || abs(n.dist(a)) > EPS)
            return false;
        if (b < a)
            swap(a, b);
        if (d < c)
            swap(c, d);
        left = max(a, c);
        right = min(b, d);
        return true;
    } else {
        left.x = right.x = -det(m.c, m.b, n.c, n.b) / zn;
        left.y = right.y = -det(m.a, m.c, n.a, n.c) / zn;
        return betw(a.x, b.x, left.x) && betw(a.y, b.y, left.y) &&
               betw(c.x, d.x, left.x) && betw(c.y, d.y, left.y);
    }
}