Advertisement
Guest User

Untitled

a guest
Nov 18th, 2018
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.29 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <math.h>
  5. #include <vector>
  6. #include <string>
  7. #include <map>
  8. #include <queue>
  9. #include <iomanip>
  10. #include <sstream>
  11. #include <random>
  12.  
  13. //#include "yanskii.h"
  14.  
  15. const double inf = 1e10;
  16.  
  17. class point {
  18. public:
  19.     double x, y, z;
  20. };
  21.  
  22. double dist(point a, point b) {
  23.     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));
  24. }
  25.  
  26. std::pair<point, point> common_per(point a1, point b1, point a2, point b2) {
  27.     // общий перпендикуляр прямых, заданных двумя точками каждая
  28.     // все, происходящее ниже, было посчитано автором в координатах на бумажке
  29.     // направляющие вектора
  30.     point v1{ b1.x - a1.x, b1.y - a1.y, b1.z - a1.z },
  31.         v2{ b2.x - a2.x, b2.y - a2.y, b2.z - a2.z };
  32.     // промежуточные выражения для уравнений
  33.     // чтобы не таскать их в формулах, предподсчитаем
  34.     double k1 = v1.x * v1.x + v1.y * v1.y + v1.z * v1.z,
  35.         k12 = v1.x * v2.x + v1.y * v2.y + v1.z * v2.z,
  36.         k2 = v2.x * v2.x + v2.y * v2.y + v2.z * v2.z,
  37.         x0 = a2.x - a1.x,
  38.         y0 = a2.y - a1.y,
  39.         z0 = a2.z - a1.z;
  40.     double c1 = v1.x * x0 + v1.y * y0 + v1.z * z0,
  41.         c2 = v2.x * x0 + v2.y * y0 + v2.z * z0;
  42.     // значения параметров уравнений данных прямых в основаниях перпендикуляра
  43.     double t1 = (-c1 * k2 + c2 * k12) / (k12 * k12 - k1 * k2);
  44.     double t2 = (-c2 + k12 * t1) / k2;
  45.     // основания перпендикуляра
  46.     point h1{ a1.x + v1.x * t1, a1.y + v1.y * t1, a1.z + v1.z * t1 },
  47.         h2{ a2.x + v2.x * t2, a2.y + v2.y * t2, a2.z + v2.z * t2 };
  48.     return { h1, h2 };
  49. }
  50.  
  51. double distance_between_point_and_segment(point c, point a, point b) {
  52.     point n = { b.x - a.x, b.y - a.y, b.z - a.z }; // направляющий вектор ab
  53.     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)) /
  54.         (n.x * n.x + n.y * n.y + n.z * n.z);
  55.     // основание перпендикуляра из c на b
  56.     point p = { a.x + n.x * t, a.y + n.y * t, a.z + n.z * t };
  57.     double ans = inf;
  58.     if (p.x >= std::min(a.x, b.x) && p.x <= std::max(a.x, b.x) &&
  59.         p.y >= std::min(a.y, b.y) && p.y <= std::max(a.y, b.y) &&
  60.         p.z >= std::min(a.z, b.z) && p.z <= std::max(a.z, b.z))
  61.     {
  62.         // если основание попало на отрезок, то улучшаем ответ
  63.         ans = dist(c, p);
  64.     }
  65.     ans = std::min(ans, dist(c, a));
  66.     ans = std::min(ans, dist(c, b));
  67.     return ans;
  68. }
  69.  
  70. double distance_between_segments(point a1, point b1, point a2, point b2) {
  71.     // проверим все варианты, где может достигаться минимум
  72.     point h1 = common_per(a1, b1, a2, b2).first,
  73.         h2 = common_per(a1, b1, a2, b2).second;
  74.     double ans = inf;
  75.     // минимум достигается на общем перпендикуляре, если он попадает на отрезки
  76.     // проверка того, что перпендикуляр к прямым попадает на отрезки
  77.     if (h1.x >= std::min(a1.x, b1.x) && h1.x <= std::max(a1.x, b1.x) &&
  78.         h1.y >= std::min(a1.y, b1.y) && h1.y <= std::max(a1.y, b1.y) &&
  79.         h1.z >= std::min(a1.z, b1.z) && h1.z <= std::max(a1.z, b1.z) &&
  80.         h2.x >= std::min(a2.x, b2.x) && h2.x <= std::max(a2.x, b2.x) &&
  81.         h2.y >= std::min(a2.y, b2.y) && h2.y <= std::max(a2.y, b2.y) &&
  82.         h2.z >= std::min(a2.z, b2.z) && h2.z <= std::max(a2.z, b2.z))
  83.     {
  84.         ans = dist (h1, h2);
  85.     }
  86.     // может достигаться на отрезке из вершины
  87.     ans = std::min(ans, distance_between_point_and_segment(a1, a2, b2));
  88.     ans = std::min(ans, distance_between_point_and_segment(b1, a2, b2));
  89.     ans = std::min(ans, distance_between_point_and_segment(a2, a1, b1));
  90.     ans = std::min(ans, distance_between_point_and_segment(b2, a1, b1));
  91.     return ans;
  92. }
  93.  
  94. void solve(std::istream& in = std::cin, std::ostream& out = std::cout) {
  95.     double x, y, z;
  96.     point p[4];
  97.     for (int i = 0; i < 4; ++i) {
  98.         in >> p[i].x >> p[i].y >> p[i].z;
  99.     }
  100.     float ans = distance_between_segments(p[0], p[1], p[2], p[3]);
  101.     out << std::setprecision(7) << std::fixed << ans << std::endl;
  102. }
  103.  
  104. void run_test(const std::string& in) {
  105.     std::stringstream out1, out2;
  106.     std::stringstream in1(in), in2(in);
  107.  
  108.     solve(in1, out1);
  109.     //solve2(in2, out2);
  110.     if (out1.str() != out2.str()) {
  111.         std::cout << in << std::endl;
  112.         std::cout << "My:      " << out1.str() << std::endl;
  113.         std::cout << "Yanskii: " << out2.str() << std::endl;
  114.         exit(1);
  115.     }
  116. }
  117.  
  118. void generate_and_run_tests(size_t count) {
  119.     for (size_t test_index = 0; test_index < count; ++test_index) {
  120.         if (test_index % 1000 == 0) {
  121.             std::cerr << "Running test " << test_index << std::endl;
  122.         }
  123.  
  124.         std::mt19937 gen(99657465789);
  125.  
  126.         std::stringstream in;
  127.  
  128.         in << std::setprecision(7) << std::fixed;
  129.  
  130.         for (int j = 0; j < 12; ++j) {
  131.             in << (double)(gen() % 2) / 1;
  132.             in << (j % 3 == 2 ? '\n' : ' ');
  133.         }
  134.  
  135.         run_test(in.str());
  136.     }
  137. }
  138.  
  139. int main() {
  140. #pragma warning(disable:4996)
  141. #ifdef _DEBUG
  142.     freopen("input.txt", "rt", stdin);
  143.     freopen("output.txt", "wt", stdout);
  144. #else
  145. #endif
  146.     //generate_and_run_tests(100000);
  147.     solve();
  148.  
  149.     return 0;
  150. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement