Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <iostream>
- #include <algorithm>
- #include <math.h>
- #include <vector>
- #include <string>
- #include <map>
- #include <queue>
- #include <iomanip>
- #include <sstream>
- #include <random>
- //#include "yanskii.h"
- const double inf = 1e10;
- class point {
- public:
- double x, y, z;
- };
- double dist(point a, point b) {
- return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z));
- }
- std::pair<point, point> common_per(point a1, point b1, point a2, point b2) {
- // общий перпендикуляр прямых, заданных двумя точками каждая
- // все, происходящее ниже, было посчитано автором в координатах на бумажке
- // направляющие вектора
- point v1{ b1.x - a1.x, b1.y - a1.y, b1.z - a1.z },
- v2{ b2.x - a2.x, b2.y - a2.y, b2.z - a2.z };
- // промежуточные выражения для уравнений
- // чтобы не таскать их в формулах, предподсчитаем
- double k1 = v1.x * v1.x + v1.y * v1.y + v1.z * v1.z,
- k12 = v1.x * v2.x + v1.y * v2.y + v1.z * v2.z,
- k2 = v2.x * v2.x + v2.y * v2.y + v2.z * v2.z,
- x0 = a2.x - a1.x,
- y0 = a2.y - a1.y,
- z0 = a2.z - a1.z;
- double c1 = v1.x * x0 + v1.y * y0 + v1.z * z0,
- c2 = v2.x * x0 + v2.y * y0 + v2.z * z0;
- // значения параметров уравнений данных прямых в основаниях перпендикуляра
- double t1 = (-c1 * k2 + c2 * k12) / (k12 * k12 - k1 * k2);
- double t2 = (-c2 + k12 * t1) / k2;
- // основания перпендикуляра
- point h1{ a1.x + v1.x * t1, a1.y + v1.y * t1, a1.z + v1.z * t1 },
- h2{ a2.x + v2.x * t2, a2.y + v2.y * t2, a2.z + v2.z * t2 };
- return { h1, h2 };
- }
- double distance_between_point_and_segment(point c, point a, point b) {
- point n = { b.x - a.x, b.y - a.y, b.z - a.z }; // направляющий вектор ab
- float t = (n.x * c.x + n.y * c.y + n.z * c.z - (n.x * a.x + n.y * a.y + n.z * a.z)) /
- (n.x * n.x + n.y * n.y + n.z * n.z);
- // основание перпендикуляра из c на b
- point p = { a.x + n.x * t, a.y + n.y * t, a.z + n.z * t };
- double ans = inf;
- if (p.x >= std::min(a.x, b.x) && p.x <= std::max(a.x, b.x) &&
- p.y >= std::min(a.y, b.y) && p.y <= std::max(a.y, b.y) &&
- p.z >= std::min(a.z, b.z) && p.z <= std::max(a.z, b.z))
- {
- // если основание попало на отрезок, то улучшаем ответ
- ans = dist(c, p);
- }
- ans = std::min(ans, dist(c, a));
- ans = std::min(ans, dist(c, b));
- return ans;
- }
- double distance_between_segments(point a1, point b1, point a2, point b2) {
- // проверим все варианты, где может достигаться минимум
- point h1 = common_per(a1, b1, a2, b2).first,
- h2 = common_per(a1, b1, a2, b2).second;
- double ans = inf;
- // минимум достигается на общем перпендикуляре, если он попадает на отрезки
- // проверка того, что перпендикуляр к прямым попадает на отрезки
- if (h1.x >= std::min(a1.x, b1.x) && h1.x <= std::max(a1.x, b1.x) &&
- h1.y >= std::min(a1.y, b1.y) && h1.y <= std::max(a1.y, b1.y) &&
- h1.z >= std::min(a1.z, b1.z) && h1.z <= std::max(a1.z, b1.z) &&
- h2.x >= std::min(a2.x, b2.x) && h2.x <= std::max(a2.x, b2.x) &&
- h2.y >= std::min(a2.y, b2.y) && h2.y <= std::max(a2.y, b2.y) &&
- h2.z >= std::min(a2.z, b2.z) && h2.z <= std::max(a2.z, b2.z))
- {
- ans = dist (h1, h2);
- }
- // может достигаться на отрезке из вершины
- ans = std::min(ans, distance_between_point_and_segment(a1, a2, b2));
- ans = std::min(ans, distance_between_point_and_segment(b1, a2, b2));
- ans = std::min(ans, distance_between_point_and_segment(a2, a1, b1));
- ans = std::min(ans, distance_between_point_and_segment(b2, a1, b1));
- return ans;
- }
- void solve(std::istream& in = std::cin, std::ostream& out = std::cout) {
- double x, y, z;
- point p[4];
- for (int i = 0; i < 4; ++i) {
- in >> p[i].x >> p[i].y >> p[i].z;
- }
- float ans = distance_between_segments(p[0], p[1], p[2], p[3]);
- out << std::setprecision(7) << std::fixed << ans << std::endl;
- }
- void run_test(const std::string& in) {
- std::stringstream out1, out2;
- std::stringstream in1(in), in2(in);
- solve(in1, out1);
- //solve2(in2, out2);
- if (out1.str() != out2.str()) {
- std::cout << in << std::endl;
- std::cout << "My: " << out1.str() << std::endl;
- std::cout << "Yanskii: " << out2.str() << std::endl;
- exit(1);
- }
- }
- void generate_and_run_tests(size_t count) {
- for (size_t test_index = 0; test_index < count; ++test_index) {
- if (test_index % 1000 == 0) {
- std::cerr << "Running test " << test_index << std::endl;
- }
- std::mt19937 gen(99657465789);
- std::stringstream in;
- in << std::setprecision(7) << std::fixed;
- for (int j = 0; j < 12; ++j) {
- in << (double)(gen() % 2) / 1;
- in << (j % 3 == 2 ? '\n' : ' ');
- }
- run_test(in.str());
- }
- }
- int main() {
- #pragma warning(disable:4996)
- #ifdef _DEBUG
- freopen("input.txt", "rt", stdin);
- freopen("output.txt", "wt", stdout);
- #else
- #endif
- //generate_and_run_tests(100000);
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement