Hướng giải của Giao điểm của hai đoạn ố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.
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ả:
Hướng dẫn giải
Kiểm tra cắt nhau bằng orientation. Nếu cắt, dùng phương pháp Cramer: \(det = (x_B-x_A)(y_D-y_C) - (y_B-y_A)(x_D-x_C)\) \(t = ((x_C-x_A)(y_D-y_C) - (y_C-y_A)(x_D-x_C)) / det\) \(x = x_A + t(x_B-x_A), y = y_A + t(y_B-y_A)\)
Nếu \(det = 0\) và các điểm thẳng hàng: kiểm tra trùng đ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 onSeg(long long x, long long y, long long xA, long long yA, long long xB, long long yB) {
return min(xA, xB) <= x && x <= max(xA, xB) &&
min(yA, yB) <= y && y <= 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);
bool intersect = false;
if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0)))
intersect = true;
else if (d1 == 0 && onSeg(xC, yC, xA, yA, xB, yB)) intersect = true;
else if (d2 == 0 && onSeg(xD, yD, xA, yA, xB, yB)) intersect = true;
else if (d3 == 0 && onSeg(xA, yA, xC, yC, xD, yD)) intersect = true;
else if (d4 == 0 && onSeg(xB, yB, xC, yC, xD, yD)) intersect = true;
if (!intersect) { cout << "NONE\n"; return 0; }
// Kiem tra collinear overlap
long long detAB = cross(xB-xA, yB-yA, xD-xC, yD-yC);
if (d1 == 0 && d2 == 0 && d3 == 0 && d4 == 0) {
cout << "SEGMENT\n"; return 0;
}
// Tinh giao diem bang Cramer
double det = (double)((xB-xA)*(yD-yC) - (yB-yA)*(xD-xC));
double t = (double)((xC-xA)*(yD-yC) - (yC-yA)*(xD-xC)) / det;
double x = xA + t * (xB - xA);
double y = yA + t * (yB - yA);
cout << "POINT " << fixed << setprecision(3) << x << " " << y << "\n";
return 0;
}
Nhận xét