Hướng giải của Mạng lưới đường ống

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải

Sử dụng orientation (tích có hướng) để kiểm tra hai đoạn cắt nhau:

  • \(d1 = cross(B-A, C-A)\), \(d2 = cross(B-A, D-A)\)
  • \(d3 = cross(D-C, A-C)\), \(d4 = cross(D-C, B-C)\)

Hai đoạn cắt nhau nếu \(d1\) và \(d2\) trái dấu, đồng thời \(d3\) và \(d4\) trái dấu. Xét thêm trường hợp đặc biệt khi điểm nằm trên đoạn.

Độ phức tạp: \(O(1)\).

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

long long cross(long long x1, long long y1, long long x2, long long y2) {
    return x1 * y2 - y1 * x2;
}

bool onSegment(long long xA, long long yA, long long xB, long long yB,
               long long xP, long long yP) {
    return min(xA, xB) <= xP && xP <= max(xA, xB) &&
           min(yA, yB) <= yP && yP <= max(yA, yB);
}

int main() {
    long long xA, yA, xB, yB, xC, yC, xD, yD;
    cin >> xA >> yA >> xB >> yB >> xC >> yC >> xD >> yD;

    long long d1 = cross(xB - xA, yB - yA, xC - xA, yC - yA);
    long long d2 = cross(xB - xA, yB - yA, xD - xA, yD - yA);
    long long d3 = cross(xD - xC, yD - yC, xA - xC, yA - yC);
    long long d4 = cross(xD - xC, yD - yC, xB - xC, yB - yC);

    if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
        ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) {
        cout << "YES\n";
        return 0;
    }
    if (d1 == 0 && onSegment(xA, yA, xB, yB, xC, yC)) { cout << "YES\n"; return 0; }
    if (d2 == 0 && onSegment(xA, yA, xB, yB, xD, yD)) { cout << "YES\n"; return 0; }
    if (d3 == 0 && onSegment(xC, yC, xD, yD, xA, yA)) { cout << "YES\n"; return 0; }
    if (d4 == 0 && onSegment(xC, yC, xD, yD, xB, yB)) { cout << "YES\n"; return 0; }
    cout << "NO\n";
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.