API tools faq
paste
Advertisement
ceva_megamind

geometry

ceva_megamind
Jul 8th, 2021
936
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 18.75 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const double PI = 3.14159265358979323846;
  6. const double EPS = 1e-8;
  7. const int INF = 1e9 + 50;
  8.  
  9. int sign(double a) {
  10.     if (abs(a) <= EPS) {
  11.         return 0;
  12.     } else if (a > EPS) {
  13.         return 1;
  14.     } else {
  15.         return -1;
  16.     }
  17. }
  18.  
  19.  
  20. struct Point {
  21.     double x;
  22.     double y;
  23.     Point (double a = 0, double b = 0) {
  24.         x = a;
  25.         y = b;
  26.     }
  27.  
  28. };
  29.  
  30.  
  31. struct Vector {
  32.     double x;
  33.     double y;
  34.     Vector (double a = 0, double b = 0) {
  35.         x = a;
  36.         y = b;
  37.     }
  38.     Vector (Point A, Point B) {
  39.         x = B.x - A.x;
  40.         y = B.y - A.y;
  41.     }
  42.     double length() {
  43.         return sqrt(x * x + y * y);
  44.     }
  45.     double length_sqared() {
  46.         return (long long)x * x + (long long)y * y;
  47.     }
  48. };
  49.  
  50.  
  51. struct Line {
  52.     double a;
  53.     double b;
  54.     double c;
  55.     Line (double x, double y, double z) {
  56.         a = x;
  57.         b = y;
  58.         c = z;
  59.     }
  60.     Line (Point A, Point B) {
  61.         b = B.x - A.x;
  62.         a = A.y - B.y;
  63.         c = -a * A.x - b * A.y;
  64.     }
  65.     Point GetPoint() {
  66.         double x = - (a * c) / (a * a + b * b);
  67.         double y = - (b * c) / (a * a + b * b);
  68.         return Point(x, y);
  69.     }
  70. };
  71.  
  72.  
  73. struct Circle {
  74.     Point C;
  75.     double r;
  76.     Circle (Point A, double b) {
  77.         C = A;
  78.         r = b;
  79.     }
  80.     Circle (double x, double y, double b) {
  81.         C = Point(x, y);
  82.         r = b;
  83.     }
  84. };
  85.  
  86.  
  87. double cross_product(Vector A, Vector B) {
  88.     return A.x * B.y - B.x * A.y;
  89. }
  90.  
  91. double dot_product(Vector A, Vector B) {
  92.     return A.x * B.x + A.y * B.y;
  93. }
  94.  
  95.  
  96. bool are_parallel_lines(Line a, Line b) {
  97.     return abs(a.a * b.b - a.b * b.a) < EPS;
  98. }
  99.  
  100. bool are_similar_lines(Line a, Line b) {
  101.     return abs(a.a * b.b - a.b * b.a) < EPS && abs(a.b * b.c - b.b * a.c) < EPS && abs(a.a * b.c - b.a * a.c) < EPS;
  102. }
  103.  
  104. Point cross_line_line(Line line1, Line line2) {
  105.     double y = (line1.c * line2.a - line1.a * line2.c) / (line1.a * line2.b - line1.b * line2.a);
  106.     double x = (line1.b * line2.c - line1.c * line2.b) / (line1.a * line2.b - line1.b * line2.a);
  107.     return Point(x, y);
  108. }
  109.  
  110. bool is_segment_intersec(Point A, Point B, Point C, Point D) {
  111.     Vector AB(A, B);
  112.     Vector CD(C, D);
  113.     Vector CA(C, A);
  114.     Vector CB(C, B);
  115.     Vector AC(A, C);
  116.     Vector AD(A, D);
  117.     Vector BC(B, C);
  118.     Vector BD(B, D);
  119.     Vector DA(D, A);
  120.     Vector DB(D, B);
  121.  
  122.     double prod1 = cross_product(AB, AC);
  123.     double prod2 = cross_product(AB, AD);
  124.     double prod3 = cross_product(CD, CA);
  125.     double prod4 = cross_product(CD, CB);
  126.  
  127.     if (abs(prod1) < EPS && abs(prod2) < EPS && abs(prod3) < EPS && abs(prod4) < EPS) { // все точки на одной прямой
  128.  
  129.         bool b1 = abs(dot_product(AC, AD) + AC.length() * AD.length()) < EPS;
  130.         bool b2 = abs(dot_product(BC, BD) + BC.length() * BD.length()) < EPS;
  131.         bool b3 = abs(dot_product(CA, CB) + CA.length() * CB.length()) < EPS;
  132.         bool b4 = abs(dot_product(DA, DB) + DA.length() * DB.length()) < EPS;
  133.  
  134.         if (b1 || b2 || b3 || b4) {
  135.             return true;
  136.         } else {
  137.             return false;
  138.         }
  139.  
  140.     } else if (prod1 * prod2 <= 0 && prod3 * prod4 <= 0) {
  141.         return true;
  142.     } else {
  143.         return false;
  144.     }
  145. }
  146.  
  147.  
  148. bool is_inside_triangle(Point P, Point A, Point B, Point C) {
  149.     Vector AB(A, B);
  150.     Vector BC(B, C);
  151.     Vector CA(C, A);
  152.     Vector AP(A, P);
  153.     Vector BP(B, P);
  154.     Vector CP(C, P);
  155.     int prod1 = sign(cross_product(AB, AP));
  156.     int prod2 = sign(cross_product(BC, BP));
  157.     int prod3 = sign(cross_product(CA, CP));
  158.     if (prod1 == 0 && prod2 == 0 && prod3 == 0) {
  159.         double max_dist_in_segment = max(max(AB.length(), BC.length()), CA.length());
  160.         double max_dist_to_point = max(max(AP.length(), BP.length()), CP.length());
  161.         return max_dist_in_segment - max_dist_to_point > -EPS;
  162.     } else if (prod1 >= 0 && prod2 >= 0 && prod3 >= 0) {
  163.         return true;
  164.     } else if (prod1 < 0 && prod2 < 0 && prod3 < 0) {
  165.         return true;
  166.     } else {
  167.         return false;
  168.     }
  169. }
  170.  
  171. bool is_inside_polygon(Point A, vector<Point> &polygon) {
  172.     int pts_num = polygon.size();
  173.     double ang = 0;
  174.     for (int i = 0; i < pts_num; ++i) {
  175.         Point pt1 = polygon[i];
  176.         Point pt2 = polygon[(i + 1) % pts_num];
  177.         Vector v1(A, pt1);
  178.         Vector v2(A, pt2);
  179.         if (abs(cross_product(v1, v2)) < EPS && dot_product(v1, v2) < EPS)
  180.             return true;
  181.         ang += atan2(cross_product(v1, v2), dot_product(v1, v2));
  182.     }
  183.     return abs(ang) > PI;
  184. }
  185.  
  186. bool is_inside_segment(Point A, Point B, Point P) {
  187.     // точка на прямой АБ
  188.     Vector AB(A, B);
  189.     Vector BA(B, A);
  190.     Vector AP(A, P);
  191.     Vector BP(B, P);
  192.     return abs(dot_product(AP, BP) + AP.length() * BP.length()) < EPS;
  193. }
  194.  
  195. bool is_inside_ray(Point A, Point B, Point P) {
  196.     Vector AB(A, B);
  197.     Vector AP(A, P);
  198.     return abs(dot_product(AB, AP) - AB.length() * AP.length()) < EPS;
  199. }
  200.  
  201. bool is_inside_convex_polygon(Point A, vector<Point> &polygon) {
  202.     int points_num = polygon.size();
  203.     Vector left_bound(polygon[0], polygon[polygon.size() - 1]);
  204.     Vector right_bound(polygon[0], polygon[1]);
  205.     Vector to_point(polygon[0], A);
  206.     if (cross_product(left_bound, to_point) < EPS && cross_product(right_bound, to_point) > -EPS) {
  207.         int left = 0;
  208.         int right = polygon.size() - 1;
  209.         while (right - left > 1) {
  210.             int mid = (left + right) / 2;
  211.             Vector diag(polygon[0], polygon[mid]);
  212.             if (cross_product(to_point, diag) > -EPS) {
  213.                 right = mid;
  214.             } else {
  215.                 left = mid;
  216.             }
  217.         }
  218.  
  219.         return is_inside_triangle(A, polygon[0], polygon[left], polygon[left + 1]);
  220.     } else {
  221.         return false;
  222.     }
  223. }
  224.  
  225.  
  226. bool is_convex(vector<Point> &polygon) {
  227.     int pts_num = polygon.size();
  228.     bool has_negative = false;
  229.     bool has_positive = false;
  230.     for (int pt = 0; pt < pts_num; ++pt) {
  231.         Point pt1 = polygon[pt];
  232.         Point pt2 = polygon[(pt + 1) % pts_num];
  233.         Point pt3 = polygon[(pt + 2) % pts_num];
  234.         Vector v12(pt1, pt2);
  235.         Vector v23(pt2, pt3);
  236.         int turn = sign(cross_product(v12, v23));
  237.         if (turn > 0)
  238.             has_positive = true;
  239.         else if (turn < 0)
  240.             has_negative = true;
  241.     }
  242.     return !(has_negative && has_positive);
  243. }
  244.  
  245.  
  246.  
  247. istream& operator>>(istream& is, Point& p) {
  248.     is >> p.x >> p.y;
  249.     return is;
  250. }
  251.  
  252. ostream& operator<<(ostream& os, Point& p) {
  253.     os << p.x << ' ' << p.y;
  254.     return os;
  255. }
  256.  
  257. Point operator + (Point A, Vector B) {
  258.     return Point(A.x + B.x, A.y + B.y);
  259. }
  260.  
  261. Point operator - (Point A, Vector B) {
  262.     return Point(A.x - B.x, A.y - B.y);
  263. }
  264.  
  265. Vector operator + (Vector A, Vector B) {
  266.     return Vector(A.x + B.x, A.y + B.y);
  267. }
  268.  
  269. Vector operator * (Vector A, double b) {
  270.     return Vector(A.x * b, A.y * b);
  271. }
  272.  
  273. Vector operator * (double b, Vector A) {
  274.     return Vector(A.x * b, A.y * b);
  275. }
  276.  
  277. Vector operator - (Vector A, Vector B) {
  278.     return Vector(A.x - B.x, A.y - B.y);
  279. }
  280.  
  281. Vector operator / (Vector A, double b) {
  282.     return Vector(A.x / b, A.y / b);
  283. }
  284.  
  285. bool operator < (const Point &A,const Point &B) {
  286.     if (abs(A.x - B.x) < EPS) {
  287.         return A.y < B.y;
  288.     } else {
  289.         return A.x < B.x;
  290.     }
  291. }
  292.  
  293. bool operator == (const Point &A, const Point & B) {
  294.     return abs(A.x - B.x) < EPS && abs(A.y - B.y) < EPS;
  295. }
  296.  
  297.  
  298. double distance_point_point (Point A, Point B) {
  299.     return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
  300. }
  301.  
  302. double distance_segment_point(Point A, Point B, Point P) {
  303.     Vector AB(A, B);
  304.     Vector BA(B, A);
  305.     Vector AP(A, P);
  306.     Vector BP(B, P);
  307.     Vector PB(P, B);
  308.     Vector PA(P, A);
  309.     double distA = distance_point_point(P, A);
  310.     double distB = distance_point_point(P, B);
  311.     if (dot_product(AB, AP) < EPS || dot_product(BA, BP) < EPS)
  312.         return min(distA, distB);
  313.     else
  314.         return abs(cross_product(PA, PB) / AB.length());
  315. }
  316.  
  317. double distance_line_point(Line f, Point A) {
  318.     return abs(f.a * A.x + f.b * A.y + f.c) / sqrt(f.a * f.a + f.b * f.b);
  319. }
  320.  
  321. double distance_ray_point(Point A, Point B, Point P) {
  322.     Vector AB(A, B);
  323.     Vector AP(A, P);
  324.     if (dot_product(AB, AP) < EPS)
  325.         return distance_point_point(P, A);
  326.     else {
  327.         return distance_line_point(Line(A, B), P);
  328.     }
  329. }
  330.  
  331. double distance_line_line(Line a, Line b) {
  332.     if (are_similar_lines(a, b))
  333.         return 0;
  334.     else if (are_parallel_lines(a, b)) {
  335.         Point P = a.GetPoint();
  336.         return distance_line_point(b, P);
  337.     } else {
  338.         return 0;
  339.     }
  340.  
  341. }
  342.  
  343. double distance_segment_segment(Point A, Point B, Point C, Point D) {
  344.     if (is_segment_intersec(A, B, C, D)) {
  345.         return 0;
  346.     } else {
  347.         return min(min(distance_segment_point(A, B, C), distance_segment_point(A, B, D)),
  348.                    min(distance_segment_point(C, D, A), distance_segment_point(C, D, B)));
  349.     }
  350. }
  351.  
  352. double distance_line_segment(Line f, Point A, Point B) {
  353.     Line g(A, B);
  354.     if (are_similar_lines(f, g))
  355.         return 0;
  356.     else if (are_parallel_lines(f, g)) {
  357.         return distance_line_point(f, A);
  358.     } else {
  359.         Point P = cross_line_line(f, g);
  360.         if (is_inside_segment(A, B, P))
  361.             return 0;
  362.         else
  363.             return min(distance_line_point(f, A), distance_line_point(f, B));
  364.     }
  365.  
  366. }
  367.  
  368. double distance_line_ray(Line f, Point A, Point B) {
  369.     Line g(A, B);
  370.     if (are_parallel_lines(f, g))
  371.         return distance_line_point(f, A);
  372.     else {
  373.         Point P = cross_line_line(f, g);
  374.         if (is_inside_ray(A, B, P))
  375.             return 0;
  376.         else
  377.             return distance_line_point(f, A);
  378.     }
  379. }
  380.  
  381. double distance_ray_ray(Point A, Point B, Point C, Point D) {
  382.     Line f(A, B);
  383.     Line g(C, D);
  384.     Vector AB(A, B);
  385.     Vector CD(C, D);
  386.     Vector CA(C, A);
  387.     Vector AC(A, C);
  388.     double edge_dist = min(distance_ray_point(C, D, A), distance_ray_point(A, B, C));
  389.     if (are_similar_lines(f, g)) {
  390.         if (abs(dot_product(AB, AC) - AB.length() * AC.length()) < EPS || abs(dot_product(CD, CA) - CD.length() * CA.length()) < EPS)
  391.             return 0;
  392.         else {
  393.             return edge_dist;
  394.         }
  395.     } else if (are_parallel_lines(f, g)) {
  396.         return edge_dist;
  397.     } else {
  398.         Point P = cross_line_line(f, g);
  399.         if (is_inside_ray(A, B, P) && is_inside_ray(C, D, P))
  400.             return 0;
  401.         else
  402.             return edge_dist;
  403.     }
  404. }
  405.  
  406. double distance_ray_segment(Point A, Point B, Point C, Point D) {
  407.     Line f(A, B);
  408.     Line g(C, D);
  409.     Vector AB(A, B);
  410.     Vector CD(C, D);
  411.     Vector CA(C, A);
  412.     Vector AC(A, C);
  413.     double edge_dist = min(min(distance_ray_point(A, B, C), distance_ray_point(A, B, D)), distance_segment_point(C, D, A));
  414.     if (are_similar_lines(f, g)) {
  415.         if (is_inside_ray(A, B, C) || is_inside_ray(A, B, D))
  416.             return 0;
  417.         else
  418.             return edge_dist;
  419.     } else if (are_parallel_lines(f, g)) {
  420.         return edge_dist;
  421.     } else {
  422.         Point P = cross_line_line(f, g);
  423.         if (is_inside_ray(A, B, P) && is_inside_segment(C, D, P))
  424.             return 0;
  425.         else {
  426.             return edge_dist;
  427.         }
  428.     }
  429. }
  430.  
  431.  
  432. bool cmp(Point A, Point B) {
  433.     if (abs(A.y * B.x - A.x * B.y) < EPS) {
  434.         return A.x * A.x + A.y * A.y < B.x * B.x + B.y * B.y;
  435.     } else {
  436.         double ang1 = atan2(A.y, A.x);
  437.         double ang2 = atan2(B.y, B.x);
  438.         return ang1 < ang2;
  439.     }
  440. }
  441.  
  442. void build_convex_hull(vector<Point> &polygon, vector<Point> &hull) {
  443.     // в центре самая нижняя левая точка, для целых чисел правильно работает, потом - хз
  444.     long long min_y = INF;
  445.     long long min_x = INF;
  446.  
  447.     for (auto pt: polygon) {
  448.         if (pt.y == min_y)
  449.             min_x = min((long long)pt.x, min_x);
  450.         else if (pt.y < min_y) {
  451.             min_y = pt.y;
  452.             min_x = pt.x;
  453.         }
  454.     }
  455.     for (int i = 0; i < polygon.size(); ++i) {
  456.         polygon[i].x -= min_x;
  457.         polygon[i].y -= min_y;
  458.     }
  459.  
  460.     sort(polygon.begin(), polygon.end(), cmp);
  461.     hull.push_back(polygon[0]);
  462.     hull.push_back(polygon[1]);
  463.     for (int i = 2; i < polygon.size(); ++i) {
  464.         while (hull.size() > 1 && cross_product(Vector(hull[hull.size() - 2], hull.back()), Vector(hull.back(), polygon[i])) < -EPS) {
  465.             hull.pop_back();
  466.         }
  467.         hull.push_back(polygon[i]);
  468.     }
  469.     for (int i = 0; i < polygon.size(); ++i) {
  470.         polygon[i].x += min_x;
  471.         polygon[i].y += min_y;
  472.     }
  473.  
  474. }
  475.  
  476. void restore_convex_polygon(vector<Point> &polygon) {
  477.     double min_x, min_y = 1e6;
  478.     for (Point pt : polygon) {
  479.         if (abs(pt.y - min_y) < EPS) {
  480.             if (pt.x < min_x) min_x = pt.x;
  481.         } else if (pt.y < min_y) {
  482.             min_y = pt.y;
  483.             min_x = pt.x;
  484.         }
  485.     }
  486.     for (int i = 0; i < polygon.size(); ++i) {
  487.         polygon[i].y -= min_y;
  488.         polygon[i].x -= min_x;
  489.         if (abs(polygon[i].y) < EPS) polygon[i].y = 0;
  490.         if (abs(polygon[i].x ) < EPS) polygon[i].x = 0;
  491.     }
  492.     sort(polygon.begin(), polygon.end(), cmp);
  493.     for (int i = 0; i < polygon.size(); ++i) {
  494.         polygon[i].y += min_y;
  495.         polygon[i].x += min_x;
  496.  
  497.     }
  498.  
  499. }
  500.  
  501. double polygon_perimeter(vector<Point> &polygon) {
  502.     double ans = 0;
  503.     for (int i = 0; i < polygon.size(); ++i)
  504.         ans += distance_point_point(polygon[i], polygon[(i + 1) % polygon.size()]);
  505.     return ans;
  506. }
  507.  
  508. double polygon_area_by_Gauss_formula(vector<Point> &polygon) {
  509.     vector<double> x_coord, y_coord;
  510.     for (Point p : polygon) {
  511.         x_coord.push_back(p.x);
  512.         y_coord.push_back(p.y);
  513.     }
  514.  
  515.     long long s = 0;
  516.     for (int i = 0; i < x_coord.size() - 1; ++i) {
  517.         s += x_coord[i] * y_coord[i + 1];
  518.     }
  519.     s += x_coord[x_coord.size() - 1] * y_coord[0];
  520.  
  521.     for (int i = 0; i < y_coord.size() - 1; ++i) {
  522.         s -= y_coord[i] * x_coord[i + 1];
  523.     }
  524.     s -= y_coord[y_coord.size() - 1] * x_coord[0];
  525.  
  526.     return abs(double(s) / 2);
  527. }
  528.  
  529. void pinpoint_turn(Line f, vector<Point> &polygon, vector<Point> &left, vector<Point> &right) {
  530.     for (Point pt : polygon) {
  531.         double eq = f.a * pt.x + f.b * pt.y + f.c;
  532.         if (eq > EPS)
  533.             right.emplace_back(pt);
  534.         else if (eq < -EPS)
  535.             left.emplace_back(pt);
  536.     }
  537. }
  538.  
  539. vector<Point> cross_line_polygon(Line f, vector<Point> &polygon) {
  540.     vector<Point> cross_pts;
  541.     for (int i = 0; i < polygon.size(); ++i) {
  542.         Point A = polygon[i];
  543.         Point B = polygon[(i + 1) % polygon.size()];
  544.         Line AB(A, B);
  545.         if (abs(AB.a * f.b - f.a * AB.b) > EPS) {
  546.             Point inter = cross_line_line(f, AB);
  547.             Vector AP(A, inter);
  548.             Vector BP(B, inter);
  549.             if ( abs(AP.length() * BP.length() + dot_product(AP, BP)) < EPS && (abs(inter.y - A.y) > EPS|| abs(inter.x - A.x) > EPS))
  550.                 cross_pts.push_back(inter);
  551.         }
  552.     }
  553.     return cross_pts;
  554. }
  555.  
  556. Point rotate_point(Point A, double angle) {
  557.     double x = A.x * cos(angle) - A.y * sin(angle);
  558.     double y = A.x * sin(angle) + A.y * cos(angle);
  559.     return Point(x, y);
  560. }
  561.  
  562. Vector rotate_vector(Vector A, double angle) {
  563.     double x = A.x * cos(angle) - A.y * sin(angle);
  564.     double y = A.x * sin(angle) + A.y * cos(angle);
  565.     return Vector(x, y);
  566. }
  567.  
  568. Point height_point(Line f, Point A) {
  569.     double dist = distance_line_point(f, A);
  570.     double x = A.x - dist * f.a / sqrt(f.a * f.a + f.b * f.b);
  571.     double y = A.y - dist * f.b / sqrt(f.a * f.a + f.b * f.b);
  572.     return Point(x, y);
  573. }
  574.  
  575. vector<Point> cross_circle_circle(Circle O1, Circle O2) {
  576.     double r1 = O1.r;
  577.     double r2 = O2.r;
  578.     vector<Point> intersection;
  579.     double d = distance_point_point(O1.C, O2.C);
  580.     if (r1 < r2) {
  581.         swap(O1, O2);
  582.         swap(r1, r2);
  583.     }
  584.  
  585.     if (O1.C == O2.C && abs(r1 - r2) < EPS) {
  586.         // бесконечность
  587.         intersection.push_back({O1.C.x, O1.C.y - r1});
  588.         intersection.push_back({O1.C.x, O1.C.y + r1});
  589.         intersection.push_back({O1.C.x + r1, O1.C.y});
  590.  
  591.     } else if (abs(d - r1 - r2) < EPS || abs(r1 - d - r2) < EPS) {
  592.         // одна
  593.         Vector O1O2(O1.C, O2.C);
  594.         Vector resized = O1O2 / O1O2.length() * r1;
  595.         Point P = O1.C + resized;
  596.         intersection.push_back(P);
  597.  
  598.     } else if (d - r1 - r2 > EPS || r1 - d - r2 > EPS) {
  599.         // ноль
  600.  
  601.     } else {
  602.         // две
  603.         Vector O1O2(O1.C, O2.C);
  604.         Vector resized = O1O2 / O1O2.length() * r1;
  605.         double ang = acos((r1 * r1 + d * d - r2 * r2) / (2 * r1 * d));
  606.         Point P1 = O1.C + rotate_vector(resized, ang);
  607.         Point P2 = O1.C + rotate_vector(resized, -ang);
  608.         intersection.push_back(P1);
  609.         intersection.push_back(P2);
  610.     }
  611.     return intersection;
  612. }
  613.  
  614. vector<Line> tangent_point_circle (Point P, Circle O) {
  615.     vector<Line> ans;
  616.     double dist = distance_point_point(P, O.C);
  617.     if (O.r < EPS) {
  618.         // окуржность - точка
  619.         ans.push_back(Line(P, O.C));
  620.     } else if (abs(O.r - dist) < EPS) {
  621.         // точка на покужности
  622.         Line f(O.C, P);
  623.         double a = -f.b;
  624.         double b = f.a;
  625.         double c = - a * P.x - b * P.y;
  626.         ans.push_back(Line(a, b, c));
  627.     } else if (dist + EPS < O.r) {
  628.         // точка в окружности
  629.     }  else {
  630.         // норм
  631.         double l = sqrt(dist * dist - O.r * O.r);
  632.         double ang = asin( O.r / dist);
  633.         Vector PC(P, O.C);
  634.         Vector norm = PC / PC.length() * l;
  635.         Vector norm_turn_1 = rotate_vector(norm, ang);
  636.         Vector norm_turn_2 = rotate_vector(norm, -ang);
  637.         Point T1 = P + norm_turn_1;
  638.         Point T2 = P + norm_turn_2;
  639.         ans.push_back(Line(P, T1));
  640.         ans.push_back(Line(P, T2));
  641.     }
  642.     return ans;
  643. }
  644.  
  645. vector<Point> cross_line_circle(Line f, Circle O) {
  646.     Point C = O.C;
  647.     double r = O.r;
  648.     vector<Point> ans;
  649.     double dist = distance_line_point(f, C);
  650.  
  651.     if (abs(dist - r) < EPS) {
  652.         ans.push_back(height_point(f, C));
  653.     } else if (abs(dist) < r) {
  654.         double l = sqrt(r * r - dist * dist);
  655.         Point H = height_point(f, C);
  656.         Vector to_point(-f.b, f.a);
  657.         to_point = to_point / to_point.length();
  658.         to_point = to_point * l;
  659.         Point A = H + to_point;
  660.         Point B = H - to_point;
  661.         if (B < A)
  662.             swap(B, A);
  663.         ans.push_back(A);
  664.         ans.push_back(B);
  665.     }
  666.     return ans;
  667. }
  668.  
  669.  
  670. int main() {
  671.     ios_base::sync_with_stdio(false);
  672.     cin.tie(0);
  673.     cout.precision(18);
  674.  
  675. }
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!