Hướng giải của Giao điểm hai đường tròn
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
Gọi \(C_1(x_1, y_1), C_2(x_2, y_2)\), khoảng cách \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\).
Khoảng cách từ \(C_1\) đến dây chung: \(a = \frac{d^2 + r_1^2 - r_2^2}{2d}\). Nửa chiều dài dây chung: \(h = \sqrt{r_1^2 - a^2}\) (nếu \(r_1^2 < a^2\) thì không có giao điểm hoặc tiếp xúc).
Vector đơn vị từ \(C_1\) đến \(C_2\): \(\vec{u} = \left(\frac{dx}{d}, \frac{dy}{d}\right)\). Vector vuông góc: \(\vec{v} = (-u_y, u_x)\).
Giao điểm: \(C_1 + a \cdot \vec{u} \pm h \cdot \vec{v}\).
Độ phức tạp: \(O(1)\).
Mã nguồn C++
#include <bits/stdc++.h>
using namespace std;
int main() {
double x1, y1, r1, x2, y2, r2;
cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
double dx = x2 - x1, dy = y2 - y1;
double d = sqrt(dx * dx + dy * dy);
const double eps = 1e-9;
if (d > r1 + r2 + eps || d < fabs(r1 - r2) - eps) {
cout << "0\n";
return 0;
}
double a = (d * d + r1 * r1 - r2 * r2) / (2.0 * d);
double h2 = r1 * r1 - a * a;
if (h2 < -eps) { cout << "0\n"; return 0; }
double ux = dx / d, uy = dy / d;
double vx = -uy, vy = ux;
double mx = x1 + a * ux, my = y1 + a * uy;
if (h2 <= eps) {
cout << "1\n";
cout << fixed << setprecision(6) << mx << " " << my << "\n";
} else {
double h = sqrt(h2);
double p1x = mx + h * vx, p1y = my + h * vy;
double p2x = mx - h * vx, p2y = my - h * vy;
cout << "2\n";
if (p1x < p2x || (fabs(p1x - p2x) <= eps && p1y < p2y)) {
cout << fixed << setprecision(6) << p1x << " " << p1y << "\n";
cout << fixed << setprecision(6) << p2x << " " << p2y << "\n";
} else {
cout << fixed << setprecision(6) << p2x << " " << p2y << "\n";
cout << fixed << setprecision(6) << p1x << " " << p1y << "\n";
}
}
return 0;
}
Nhận xét