Hướng dẫn giải của [Beginner Free Contest 05] 3DGEOMETRY
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cho T bộ dữ liệu, mỗi bộ là tọa độ ba điểm A, B, C trong không gian 3 chiều. In khoảng cách từ A đến đường thẳng BC, làm tròn 2 chữ số thập phân.
Sub 1: Tìm hình chiếu rồi đo khoảng cách — ~O(T)~
Tìm điểm H là hình chiếu của A lên đường thẳng BC bằng tích vô hướng: H = B + t·(C − B) với t = ((A − B)·(C − B)) / |C − B|². Sau đó khoảng cách là |AH|. Cách này dễ nghĩ, dùng tọa độ thực (long double) và đạt 2/2 test của bài.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
long double xa, ya, za, xb, yb, zb, xc, yc, zc;
cin >> xa >> ya >> za >> xb >> yb >> zb >> xc >> yc >> zc;
// Sub 1: tim hinh chieu H cua A len duong thang BC bang tich vo huong,
// roi tinh |AH| truc tiep (khong dung tich co huong).
long double dx = xc - xb, dy = yc - yb, dz = zc - zb;
long double len2 = dx * dx + dy * dy + dz * dz;
long double ux = xa - xb, uy = ya - yb, uz = za - zb;
long double tt = (ux * dx + uy * dy + uz * dz) / len2;
long double hx = xb + tt * dx, hy = yb + tt * dy, hz = zb + tt * dz;
long double d = sqrtl((xa - hx) * (xa - hx) + (ya - hy) * (ya - hy) + (za - hz) * (za - hz));
printf("%.2Lf\n", d);
}
return 0;
}
Sub 2: Dùng tích có hướng — ~O(T)~
Công thức gọn hơn: khoảng cách từ A đến đường thẳng BC bằng |BA × BC| / |BC|, với × là tích có hướng của hai vector. Tích có hướng cho diện tích hình bình hành, nên chia độ dài của nó cho độ dài đáy BC sẽ ra chiều cao từ A xuống BC.
Bẫy cần chú ý: tọa độ có thể lên tới 10^9 nên các tích và tổng bình phương vượt long long. Vì vậy dùng long double cho toàn bộ phép tính và in bằng %.2Lf. Đạt 2/2 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
long double xa, ya, za, xb, yb, zb, xc, yc, zc;
cin >> xa >> ya >> za >> xb >> yb >> zb >> xc >> yc >> zc;
// Khoang cach tu A den duong thang BC = |BA x BC| / |BC|
long double ux = xa - xb, uy = ya - yb, uz = za - zb; // vector BA
long double vx = xc - xb, vy = yc - yb, vz = zc - zb; // vector BC
// Tich co huong BA x BC (dung long double de tranh tran so)
long double cx = uy * vz - uz * vy;
long double cy = uz * vx - ux * vz;
long double cz = ux * vy - uy * vx;
long double d = sqrtl(cx * cx + cy * cy + cz * cz) / sqrtl(vx * vx + vy * vy + vz * vz);
printf("%.2Lf\n", d);
}
return 0;
}
Bình luận