API tools faq
paste
Advertisement
ekzolot

Untitled

ekzolot
Nov 27th, 2023
585
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.54 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. double mod(double x){
  5.     if (x<0){
  6.         x=-x;
  7.     }
  8.     return x;
  9. }
  10. bool equal(double a, double b){
  11.     if (mod(a-b)<eps){
  12.         return true;
  13.     }
  14.     return false;
  15. }
  16. bool less_than(double a, double b){
  17.     if (a<b-eps){
  18.         return true;
  19.     }
  20.     return false;
  21. }
  22. bool less_than_or_equal_to(double a, double b){
  23.     if (less_than(a, b) || equal(a, b)){
  24.         return true;
  25.     }
  26.     return false;
  27. }
  28. int sign(double a){
  29.     if (less_than(a, 0)){
  30.         return -1;
  31.     }
  32.     if (equal(a, 0)){
  33.         return 0;
  34.     }
  35.     return 1;
  36. }
  37. struct Point{
  38.     double x;
  39.     double y;
  40. };
  41. struct Line{
  42.     double a;
  43.     double b;
  44.     double c;
  45. };
  46. struct Circle{
  47.     Point o;
  48.     double r;
  49. };
  50. bool equal_points(Point p, Point q){
  51.     if (equal(p.x, q.x) && equal(p.y, q.y)){
  52.         return true;
  53.     }
  54.     return false;
  55. }
  56. Point draw_vector(Point p, Point q){
  57.     return {q.x-p.x, q.y-p.y};
  58. }
  59. Point sum_of_two_points(Point p, Point q){
  60.     return {p.x+q.x, p.y+q.y};
  61. }
  62. double cross_product(Point p, Point q){
  63.     return p.x*q.x+p.y*q.y;
  64. }
  65. double dot_product(Point p, Point q){
  66.     return p.x*q.y-p.y*q.x;
  67. }
  68. Point change_length(Point p, double l){
  69.     return {(p.x*l)/(sqrt(p.x*p.x+p.y*p.y)), (p.y*l)/(sqrt(p.x*p.x+p.y*p.y))};
  70. }
  71. Point rotate_90_deg(Point p){
  72.     return {-p.y, p.x};
  73. }
  74. double angle_between_vectors(Point p, Point q){
  75.     return atan2(dot_product(p, q), cross_product(p, q));
  76. }
  77. double distance_between_two_points(Point p, Point q){
  78.     return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y));
  79. }
  80. Line line_by_two_points(Point p, Point q){
  81.     return {q.y-p.y, p.x-q.x, p.y*q.x-p.x*q.y};
  82. }
  83. bool check_if_3_points_are_collinear(Point p, Point q, Point r){
  84.     if (equal(dot_product(draw_vector(q, p), draw_vector(q, r)), 0)){
  85.         return true;
  86.     }
  87.     return false;
  88. }
  89. bool same_lines(Line f, Line g){
  90.     if (!equal(f.a*g.b,g.a*f.b)){
  91.         return false;
  92.     }
  93.     if (!equal(f.a*g.c, f.c*g.a)){
  94.         return false;
  95.     }
  96.     return true;
  97. }
  98. bool parallel_lines(Line f, Line g){
  99.     if (same_lines(f, g)){
  100.         return false;
  101.     }
  102.     if (equal(f.a*g.b, f.b*g.a)){
  103.         return true;
  104.     }
  105.     return false;
  106. }
  107. Point intersection_of_two_lines(Line f, Line g){
  108.     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))};
  109. }
  110. double distance_from_point_to_line(Point p, Line f){
  111.     return (abs(f.a*p.x+f.b*p.y+f.c))/sqrt(f.a*f.a+f.b*f.b);
  112. }
  113. Point base_of_a_perpendicular(Point p, Line f){
  114.     if (equal(distance_from_point_to_line(sum_of_two_points(p, change_length({f.a, f.b}, distance_from_point_to_line(p, f))), f), 0)){
  115.         return sum_of_two_points(p, change_length({f.a, f.b}, distance_from_point_to_line(p, f)));
  116.     }
  117.     Point r=change_length({f.a, f.b}, distance_from_point_to_line(p, f));
  118.     Point q;
  119.     q.x=-r.x;
  120.     q.y=-r.y;
  121.     return sum_of_two_points(p, q);
  122. }
  123. double distance_from_point_to_segment(Point r, Point p, Point q){
  124.     if (less_than(cross_product(draw_vector(q, p), draw_vector(q, r)), (double) 0)){
  125.         return distance_between_two_points(q, r);
  126.     }
  127.     if (less_than(cross_product(draw_vector(p, q), draw_vector(p, r)), (double) 0)){
  128.         return distance_between_two_points(p, r);
  129.     }
  130.     return distance_from_point_to_line(r, line_by_two_points(p, q));
  131. }
  132. bool two_segments_intersect(Point a, Point b, Point c, Point d){
  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 segment_intersect_ray(Point a, Point b, Point c, Point d){
  168.     if (equal(dot_product(draw_vector(c, a), draw_vector(c, d)), 0)){
  169.         if (equal(dot_product(draw_vector(c, b), draw_vector(c, d)), 0)){
  170.             if (less_than(0, cross_product(draw_vector(c, a), draw_vector(c, d)))){
  171.                 return true;
  172.             }
  173.             if(less_than(0, cross_product(draw_vector(c, b), draw_vector(c, d)))){
  174.                 return true;
  175.             }
  176.         }
  177.         if (less_than(0, cross_product(draw_vector(c, a), draw_vector(c, d)))){
  178.             return true;
  179.         }
  180.         return false;
  181.     }
  182.     if (equal(dot_product(draw_vector(c, b), draw_vector(c, d)), 0)){
  183.         if (less_than_or_equal_to(0, cross_product(draw_vector(c, b), draw_vector(c, d)))){
  184.             return true;
  185.         }
  186.         return false;
  187.     }
  188.     if (sign(dot_product(draw_vector(c, d), draw_vector(c, a)))!=sign(dot_product(draw_vector(c, d), draw_vector(c, b)))){
  189.         Point x= intersection_of_two_lines(line_by_two_points(a, b), line_by_two_points(c, d));
  190.         if (less_than_or_equal_to(0, cross_product(draw_vector(c, x), draw_vector(c, d)))){
  191.             return true;
  192.         }
  193.         return false;
  194.     }
  195.     return false;
  196. }
  197. double distance_from_segment_to_ray(Point a, Point b, Point c, Point d) {
  198.     Line f = line_by_two_points(c, d);
  199.     Line g = line_by_two_points(a, b);
  200.     if (segment_intersect_ray(a, b, c, d)) {
  201.         return 0;
  202.     } else {
  203.         Point h2 = base_of_a_perpendicular(c, g);
  204.         double d5;
  205.         if (less_than(cross_product(draw_vector(c, d), draw_vector(c, a)), 0)) {
  206.             d5 = distance_between_two_points(a, c);
  207.         } else {
  208.             d5 = distance_from_point_to_line(a, f);
  209.         }
  210.         double d6;
  211.         if (less_than(cross_product(draw_vector(c, d), draw_vector(c, b)), 0)) {
  212.             d6 = distance_between_two_points(b, c);
  213.         } else {
  214.             d6 = distance_from_point_to_line(b, f);
  215.         }
  216.         double minimum = min(d5, d6);
  217.         if (less_than_or_equal_to(cross_product(draw_vector(h2, a), draw_vector(h2, b)), 0)) {
  218.             minimum = min(minimum, distance_between_two_points(c, h2));
  219.         }
  220.         return minimum;
  221.     }
  222. }
  223. double distance_from_point_to_ray(Point c, Point a, Point b){
  224.     Point h = base_of_a_perpendicular(c, line_by_two_points(a, b));
  225.     if (less_than_or_equal_to(0, cross_product(draw_vector(a, h), draw_vector(a, b)))){
  226.         return distance_from_point_to_line(c, line_by_two_points(a, b));
  227.     }
  228.     return distance_between_two_points(c, a);
  229. }
  230. double distance_between_rays(Point a, Point b, Point c, Point d){
  231.     if (parallel_lines(line_by_two_points(a, b), line_by_two_points(c, d)) || same_lines(line_by_two_points(a, b), line_by_two_points(c, d))) {
  232.         return min(distance_from_point_to_ray(a, c, d), distance_from_point_to_ray(c, a, b));
  233.     }
  234.     Point f = intersection_of_two_lines(line_by_two_points(a, b), line_by_two_points(c, d));
  235.     if (less_than_or_equal_to(0, cross_product(draw_vector(a, b), draw_vector(a, f)))) {
  236.         if (less_than_or_equal_to(0, cross_product(draw_vector(c, d), draw_vector(c, f)))) {
  237.             return 0;
  238.         }
  239.     }
  240.     return min(distance_from_point_to_ray(a, c, d), distance_from_point_to_ray(c, a, b));
  241. }
  242. double distance_from_ray_to_line(Point a, Point b, Line f){
  243.     if (parallel_lines(line_by_two_points(a, b), f) || same_lines(line_by_two_points(a, b), f)){
  244.         return distance_from_point_to_line(a, f);
  245.     }
  246.     Point x= intersection_of_two_lines(line_by_two_points(a, b), f);
  247.     if (less_than_or_equal_to(0, cross_product(draw_vector(a, x), draw_vector(a, b)))){
  248.         return 0;
  249.     }
  250.     return distance_from_point_to_line(a, f);
  251. }
  252. double distance_between_lines(Line g, Line f, Point a){
  253.     if (same_lines(f, g)){
  254.         return 0;
  255.     }
  256.     if (parallel_lines(f, g)){
  257.         return distance_from_point_to_line(a, f);
  258.     }
  259.     return 0;
  260. }
  261. bool point_inside_of_circle(Point p, Circle omega){
  262.     return less_than(distance_between_two_points(p, omega.o), omega.r);
  263. }
  264. bool point_lie_on_circle(Point p, Circle omega){
  265.     return equal(distance_between_two_points(p, omega.o), omega.r);
  266. }
  267. bool point_outside_of_circle(Point p, Circle omega){
  268.     return ((!point_inside_of_circle(p, omega)) && (!point_lie_on_circle(p, omega)));
  269. }
  270. bool line_tangent_circle(Line f, Circle omega){
  271.     return equal(distance_from_point_to_line(omega.o, f), omega.r);
  272. }
  273. bool line_intersect_circle(Line f, Circle omega){
  274.     return less_than(distance_from_point_to_line(omega.o, f), omega.r);
  275. }
  276. Point tangency_point(Line f, Circle omega){
  277.     return base_of_a_perpendicular(omega.o, f);
  278. }
  279. pair<Point, Point> intersection_points_line_circle(Line f, Circle omega){
  280.     double d = distance_from_point_to_line(omega.o, f);
  281.     Point p1, p2;
  282.     p1 = sum_of_two_points(base_of_a_perpendicular(omega.o, f), change_length(rotate_90_deg({f.a, f.b}), sqrt(omega.r*omega.r-d*d)));
  283.     p2 = sum_of_two_points(base_of_a_perpendicular(omega.o, f), change_length(rotate_90_deg({-f.a, -f.b}), sqrt(omega.r*omega.r-d*d)));
  284.     return {p1, p2};
  285. }
  286. int main(){
  287.     int t;
  288.     cin>>t;
  289.     cout.precision(20);
  290.     while(t--){
  291.         Circle omega1, omega2;
  292.         cin>>omega1.o.x>>omega1.o.y>>omega1.r>>omega2.o.x>>omega2.o.y>>omega2.r;
  293.         if (equal_points(omega1.o, omega2.o) && equal(omega1.r, omega2.r)){
  294.             cout<<3<<"\n";
  295.             continue;
  296.         }
  297.         Circle newc1, newc2;
  298.         newc1.o={0, 0};
  299.         newc1.r=omega1.r;
  300.         newc2.o={omega2.o.x-omega1.o.x, omega2.o.y-omega1.o.y};
  301.         newc2.r=omega2.r;
  302.         Line g = {2*newc2.o.x, 2*newc2.o.y, newc2.r*newc2.r-newc1.r*newc1.r-newc2.o.x*newc2.o.x-newc2.o.y*newc2.o.y};
  303.         if (line_tangent_circle(g, newc2)){
  304.             Point p1 = tangency_point(g, newc2);
  305.             cout<<1<<"\n";
  306.             cout<<p1.x+omega1.o.x<<" "<<p1.y+omega1.o.y<<"\n";
  307.             continue;
  308.         }
  309.         if (line_intersect_circle(g, newc2)){
  310.             pair<Point, Point> p= intersection_points_line_circle(g, newc2);
  311.             Point q1, q2;
  312.             q1.x=p.first.x+omega1.o.x;
  313.             q1.y=p.first.y+omega1.o.y;
  314.             q2.x=p.second.x+omega1.o.x;
  315.             q2.y=p.second.y+omega1.o.y;
  316.             Line f = line_by_two_points(omega1.o, omega2.o);
  317.             Point H= base_of_a_perpendicular(q1, f);
  318.             cout<<2<<"\n";
  319.             cout<<H.x<<" "<<H.y<<"\n";
  320.             cout<<distance_between_two_points(omega1.o, H)<<" "<<distance_from_point_to_line(q1, f)<<"\n";
  321.             cout<<q1.x<<" "<<q1.y<<"\n";
  322.             cout<<q2.x<<" "<<q2.y<<"\n";
  323.             continue;
  324.         }
  325.         cout<<0<<"\n";
  326.         continue;
  327.     }
  328. }
  329.  
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!