API tools faq
paste
Advertisement
ekzolot

Untitled

ekzolot
Oct 17th, 2023
546
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.88 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. double eps=1e-6;
  4. bool less_than(double a, double b){
  5.     return a<b-eps;
  6. }
  7. bool equal(double a, double b){
  8.     return abs(a-b)<eps;
  9. }
  10. bool less_than_or_equal_to(double a, double b){
  11.     return (equal(a, b) || less_than(a, b));
  12. }
  13. int sign(double a){
  14.     if (less_than(a, 0)){
  15.         return -1;
  16.     }
  17.     if (equal(a, 0)){
  18.         return 0;
  19.     }
  20.     return 1;
  21. }
  22. struct Point{
  23.     double x;
  24.     double y;
  25. };
  26. struct Line{
  27.     double a;
  28.     double b;
  29.     double c;
  30. };
  31. struct Circle{
  32.     Point o;
  33.     double r;
  34. };
  35. bool equal_points(Point p, Point q){
  36.     return (equal(p.x, q.x) && equal(p.y, q.y));
  37. }
  38. Point draw_vector(Point p, Point q){
  39.     return {q.x-p.x, q.y-p.y};
  40. }
  41. Point sum_of_vectors(Point p, Point q){
  42.     return {p.x+q.x, p.y+q.y};
  43. }
  44. double cross_product(Point p, Point q){
  45.     return p.x*q.x+p.y*q.y;
  46. }
  47. double dot_product(Point p, Point q){
  48.     return p.x*q.y-p.y*q.x;
  49. }
  50. double length_vector(Point p){
  51.     return sqrt(p.x*p.x+p.y*p.y);
  52. }
  53. Point change_length(Point p, double l){
  54.     return {(l*p.x)/(sqrt(p.x*p.x+p.y*p.y)), (l*p.y)/(sqrt(p.x*p.x+p.y*p.y))};
  55. }
  56. Point rotate_90_deg(Point p){
  57.     return {-p.y, p.x};
  58. }
  59. double angle_between_vectors(Point p, Point q){
  60.     return atan2(dot_product(p, q), cross_product(p, q));
  61. }
  62. double distance_points(Point p, Point q){
  63.     return length_vector(draw_vector(p, q));
  64. }
  65. Line line_by_two_points(Point p, Point q){
  66.     return {q.y-p.y, p.x-q.x, p.y*q.x-p.x*q.y};
  67. }
  68. bool three_points_collinear(Point p, Point q, Point r){
  69.     return equal(0, dot_product(draw_vector(p, q), draw_vector(p, r)));
  70. }
  71. bool point_lie_on_segment(Point r, Point p, Point q){
  72.     if (!three_points_collinear(p, q, r)){
  73.         return false;
  74.     }
  75.     if (equal_points(r, p) || equal_points(r, q)){
  76.         return true;
  77.     }
  78.     if (equal_points(p, q)){
  79.         return equal_points(p, r);
  80.     }
  81.     return less_than_or_equal_to(cross_product(draw_vector(r, p), draw_vector(r, q)), 0);
  82. }
  83. bool same_lines(Line f, Line g){
  84.     if (!equal(f.a*g.b,g.a*f.b)){
  85.         return false;
  86.     }
  87.     if (!equal(f.a*g.c, f.c*g.a)){
  88.         return false;
  89.     }
  90.     return true;
  91. }
  92. bool parallel_lines(Line f, Line g){
  93.     if (same_lines(f, g)){
  94.         return false;
  95.     }
  96.     if (equal(f.a*g.b, f.b*g.a)){
  97.         return true;
  98.     }
  99.     return false;
  100. }
  101. Point intersection_two_lines(Line f, Line g){
  102.     return {(f.c*g.b-f.b*g.c)/(1.0*(f.b*g.a-g.b*f.a)), (f.c*g.a-g.c*f.a)/(1.0*(f.a*g.b-g.a*f.b))};
  103. }
  104. double distance_point_line(Point p, Line f){
  105.     return (abs(p.x*f.a+p.y*f.b+f.c))/sqrt(f.a*f.a+f.b*f.b);
  106. }
  107. Point base_of_perpendicular(Point p, Line f){
  108.     if (equal(distance_point_line(sum_of_vectors(p, change_length({f.a, f.b}, distance_point_line(p, f))), f), 0)){
  109.         return sum_of_vectors(p, change_length({f.a, f.b}, distance_point_line(p, f)));
  110.     }
  111.     return sum_of_vectors(p, change_length({-f.a, -f.b}, distance_point_line(p, f)));
  112. }
  113. double distance_point_segment(Point r, Point p, Point q){
  114.     if (equal_points(p, q)){
  115.         return distance_points(p, r);
  116.     }
  117.     Point H= base_of_perpendicular(r, line_by_two_points(p, q));
  118.     if (point_lie_on_segment(H, p, q)){
  119.         return distance_points(r, H);
  120.     }
  121.     return min(distance_points(r, p), distance_points(r, q));
  122. }
  123. bool two_segments_intersect(Point a, Point b, Point c, Point d){
  124.     if (equal_points(a, b)){
  125.         return three_points_collinear(a, c, d);
  126.     }
  127.     if (equal_points(c, d)){
  128.         return three_points_collinear(a, b, c);
  129.     }
  130.     if (equal_points(a, c) || equal_points(a, d) || equal_points(b, c) || equal_points(b, d)){
  131.         return true;
  132.     }
  133.     if (equal(dot_product(draw_vector(c, a), draw_vector(c, d)), 0)){
  134.         if (equal(dot_product(draw_vector(c, b), draw_vector(c, d)), 0)) {
  135.             if (less_than_or_equal_to(cross_product(draw_vector(a, c), draw_vector(a, d)), 0)){
  136.                 return true;
  137.             }
  138.             if (less_than_or_equal_to(cross_product(draw_vector(b, c), draw_vector(b, d)), 0)){
  139.                 return true;
  140.             }
  141.             if (less_than_or_equal_to(cross_product(draw_vector(c, a), draw_vector(c, b)), 0)){
  142.                 return true;
  143.             }
  144.             if (less_than_or_equal_to(cross_product(draw_vector(d, a), draw_vector(d, b)), 0)){
  145.                 return true;
  146.             }
  147.             return false;
  148.         }
  149.         if (less_than_or_equal_to(cross_product(draw_vector(a, c), draw_vector(a, d)), 0)){
  150.             return true;
  151.         }
  152.         return false;
  153.     }
  154.     if (equal(dot_product(draw_vector(c, b), draw_vector(c, d)), 0)){
  155.         if (less_than_or_equal_to(cross_product(draw_vector(b, c), draw_vector(b, d)), 0)){
  156.             return true;
  157.         }
  158.         return false;
  159.     }
  160.     if (sign(dot_product(draw_vector(c, d), draw_vector(c, a)))!=sign(dot_product(draw_vector(c, d), draw_vector(c, b)))){
  161.         if (sign(dot_product(draw_vector(a, b), draw_vector(a, c)))!=sign(dot_product(draw_vector(a, b), draw_vector(a, d)))){
  162.             return true;
  163.         }
  164.     }
  165.     return false;
  166. }
  167. bool point_lie_on_ray(Point r, Point p, Point q){
  168.     if (!three_points_collinear(r, p, q)){
  169.         return false;
  170.     }
  171.     if (equal_points(r, p) || equal_points(r, q)){
  172.         return true;
  173.     }
  174.     return (less_than_or_equal_to(0, cross_product(draw_vector(p, r), draw_vector(p, q))));
  175. }
  176. double distance_point_ray(Point r, Point p, Point q){
  177.     Point H = base_of_perpendicular(r, line_by_two_points(p, q));
  178.     if (point_lie_on_ray(H, p, q)){
  179.         return distance_points(r, H);
  180.     }
  181.     return distance_points(r, p);
  182. }
  183. bool segment_intersect_ray(Point p, Point q, Point r, Point s){
  184.     Line f= line_by_two_points(p, q);
  185.     Line g= line_by_two_points(r, s);
  186.     if (same_lines(f, g)){
  187.         return (point_lie_on_ray(p, r, s) || point_lie_on_ray(q, r, s));
  188.     }
  189.     if (parallel_lines(f, g)){
  190.         return false;
  191.     }
  192.     Point t = intersection_two_lines(f, g);
  193.     return (point_lie_on_segment(t, p, q) && point_lie_on_ray(t, r, s));
  194. }
  195. double distance_segment_ray(Point p, Point q, Point r, Point s){
  196.     if (equal_points(p, q)){
  197.         return distance_point_ray(p, r, s);
  198.     }
  199.     if (segment_intersect_ray(p, q, r, s)){
  200.         return 0;
  201.     }
  202.     double minimum= distance_point_segment(r, p, q);
  203.     Point h1 = base_of_perpendicular(p, line_by_two_points(r, s));
  204.     Point h2 = base_of_perpendicular(q, line_by_two_points(r, s));
  205.     if (point_lie_on_ray(h1, r, s)){
  206.         minimum=min(minimum, distance_points(p, h1));
  207.     }
  208.     if (point_lie_on_ray(h2, r, s)){
  209.         minimum=min(minimum, distance_points(q, h2));
  210.     }
  211.     return minimum;
  212. }
  213. bool rays_intersect(Point p, Point q, Point r, Point s){
  214.     if (equal_points(p, q)){
  215.         return point_lie_on_ray(p, r, s);
  216.     }
  217.     if (equal_points(r, s)){
  218.         return point_lie_on_ray(r, p, q);
  219.     }
  220.     Line f = line_by_two_points(p, q);
  221.     Line g = line_by_two_points(r, s);
  222.     if (same_lines(f, g)){
  223.         if (less_than_or_equal_to(0, cross_product(draw_vector(p, q), draw_vector(r, s)))){
  224.             return true;
  225.         }
  226.         if (point_lie_on_ray(p, r, s) || point_lie_on_ray(r, p, q)){
  227.             return true;
  228.         }
  229.         return false;
  230.     }
  231.     if (parallel_lines(f, g)){
  232.         return false;
  233.     }
  234.     Point t= intersection_two_lines(f, g);
  235.     return (point_lie_on_ray(t, p, q) && point_lie_on_ray(t, r, s));
  236. }
  237. double distance_rays(Point p, Point q, Point r, Point s) {
  238.     if (rays_intersect(p, q, r, s)) {
  239.         return 0;
  240.     }
  241.     Line f = line_by_two_points(p, q);
  242.     Line g = line_by_two_points(r, s);
  243.     if (same_lines(f, g)) {
  244.         return distance_points(p, r);
  245.     }
  246.     if (parallel_lines(f, g)) {
  247.         Point h1 = base_of_perpendicular(p, g);
  248.         Point h2 = base_of_perpendicular(r, f);
  249.         if (point_lie_on_ray(h1, r, s)) {
  250.             return distance_points(h1, p);
  251.         }
  252.         if (point_lie_on_ray(h2, p, q)) {
  253.             return distance_points(h2, r);
  254.         }
  255.         return distance_points(p, r);
  256.     }
  257.     return min(distance_point_ray(p, r, s), distance_point_ray(r, p, q));
  258. }
  259. bool ray_intersect_line(Point p, Point q, Line f){
  260.     Line g= line_by_two_points(p, q);
  261.     if (same_lines(f, g)){
  262.         return true;
  263.     }
  264.     if (parallel_lines(f, g)){
  265.         return false;
  266.     }
  267.     Point t= intersection_two_lines(f, g);
  268.     return point_lie_on_ray(t, p, q);
  269. }
  270. double distance_segments(Point p, Point q, Point r, Point s){
  271.     if (two_segments_intersect(p, q, r, s)){
  272.         return 0;
  273.     }
  274.     double d1 = distance_point_segment(p, r, s);
  275.     double d2 = distance_point_segment(q, r, s);
  276.     double d3 = distance_point_segment(r, p, q);
  277.     double d4 = distance_point_segment(s, p, q);
  278.     return min(d4, min(d3, min(d2, d1)));
  279. }
  280. double distance_ray_line(Point p, Point q, Line f){
  281.     if (ray_intersect_line(p, q, f)){
  282.         return 0;
  283.     }
  284.     Line g= line_by_two_points(p, q);
  285.     if (parallel_lines(f, g)){
  286.         return distance_point_line(p, f);
  287.     }
  288.     return distance_point_line(p, f);
  289. }
  290. double distance_segment_lime(Point p, Point q, Line f){
  291.     return min(distance_point_line(p, f), distance_point_line(q, f));
  292. }
  293. double distance_lines(Line f, Line g){
  294.     if (same_lines(f, g)){
  295.         return 0;
  296.     }
  297.     if (parallel_lines(f, g)){
  298.         Point r;
  299.         if (f.a!=0){
  300.             r={-f.c/f.a, 0};
  301.         }else{
  302.             r={0, -f.c/f.b};
  303.         }
  304.         return distance_point_line(r, g);
  305.     }
  306.     return 0;
  307. }
  308. int main(){
  309.     Point a, b, c, d;
  310.     cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y>>d.x>>d.y;
  311.     Line f= line_by_two_points(a, b);
  312.     Line g= line_by_two_points(c, d);
  313.     cout<<distance_points(a, c)<<"\n";
  314.     cout<<distance_point_segment(a, c, d)<<"\n";
  315.     cout<<distance_point_ray(a, c, d)<<"\n";
  316.     cout<<distance_point_line(a, g)<<"\n";
  317.     cout<<distance_point_segment(c, a, b)<<"\n";
  318.  
  319. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!