Advertisement
999ms

Untitled

Nov 6th, 2019
184
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.36 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define all(x) (x).begin(),(x).end()
  3.  
  4. using namespace std;
  5. using ll = long long;
  6. using ld = long double;
  7. const ld PI = acosl(-1.0);
  8.  
  9.  
  10. ld IntersectCircles(int r1, int r2, int x, int y) {
  11.     ld dist = sqrtl(x * x + y * y);
  12.     if (dist >= r1 + r2) return 0;
  13.     if (r1 < r2) swap(r1, r2);
  14.     if (dist + r2 <= r1) return PI * r2 * r2;
  15.     ld cosA = (r1 * r1 + dist * dist - r2 * r2) * 0.5 / dist / r1;
  16.     ld A = acosl(cosA);
  17.     ld cosB = (r2 * r2 + dist * dist - r1 * r1) * 0.5 / dist / r2;
  18.     ld B = acosl(cosB);
  19.     ld firstAns = (A - sinl(A + A)) * r1 * r1;
  20.     ld secondAns = (B - sinl(B + B)) * r2 * r2;
  21.     return firstAns + secondAns;
  22. }
  23.  
  24. ld IntersectCircles(int x1, int y1, int r1, int x2, int y2, int r2) {
  25.     return IntersectCircles(r1, r2, x2 - x1, y2 - y1);
  26. }
  27.  
  28. ld FindSegment(ld r, ld h) {
  29.     h = abs(h);
  30.     if (h >= r) return 0;
  31.     ld cosA = h / r;
  32.     ld A = acosl(cosA);
  33.     return (PI - A) * r * r;
  34. }
  35.  
  36. ld Case1(ld h, ld g, ld r) {
  37.     ld a = sqrtl(r * r - g * g) - h;
  38.     ld b = sqrtl(r * r - h * h) - g;
  39.     ld ans = a * b / 2;
  40.     ld c = sqrtl(a * a + b * b) / 2;
  41.     ld d = sqrtl(r * r - c * c);
  42.     return ans + FindSegment(r, d);
  43. }
  44.  
  45. ld Do(int x, int y, int r) {
  46.     const int R = 60;
  47.     x = abs(x);
  48.     ld ans = IntersectCircles(R, r, x, y);
  49.     ld f = sqrtl(r * r - y * y);
  50.     ld left = x - f;
  51.     ld right = x + f;
  52.     if (-R <= left && right <= R) {
  53.         return ans - FindSegment(r, y);
  54.     }
  55.     left = 0;
  56.     right = R;
  57.     ld mid;
  58.     ld a, b;
  59.     ld up = 0;
  60.     ld down = 0;
  61.     for (int i = 0; i < 100; i++) {
  62.         mid = (left + right) / 2;
  63.         a = sqrtl(R * R - mid * mid);
  64.         b = y + sqrtl(r * r - (x - mid) * (x - mid));
  65.         if (a > b) {
  66.             right = mid;
  67.         } else {
  68.             left = mid;
  69.         }
  70.     }
  71.     up = mid;
  72.     left = 0;
  73.     right = R;
  74.     for (int i = 0; i < 100; i++) {
  75.         mid = (left + right) / 2;
  76.         a = - sqrtl(R * R - mid * mid);
  77.         b = - y - sqrtl(r * r - (x - mid) * (x - mid));
  78.         if (a < b) {
  79.             right = mid;
  80.         } else {
  81.             left = mid;
  82.         }
  83.     }
  84.     down = mid;
  85.     if (down > up) {
  86.         ld sub = Case1(0, up, R) + Case1(x - up, 0 - y, r);
  87.         ans -= sub;
  88.     } else {
  89.         ans = Case1(0, down, R) + Case1(x - down, 0 - y, r);
  90.     }
  91.     return ans;
  92. }
  93.  
  94. ld IntersectCircleAndHalfOfCircle(int r1, int r2, int x, int y) {
  95.     if (r1 < y) return IntersectCircles(r1, r2, x, y);
  96.     if (y < -r1) return 0;
  97.     ld dist = sqrtl(x * x + y * y);
  98.     if (dist >= r1 + r2) return 0;
  99.     if (r1 > r2) {
  100.         if (dist + r2 <= r1) {
  101.             return PI * r2 * r2 / 2;
  102.         }
  103.     }
  104.     return Do(-x, -y, r1);
  105. }
  106.  
  107. ld IntersectCircleAndHalfOfCircle(int x1, int y1, int r1, int x2, int y2, int r2) {
  108.     return IntersectCircleAndHalfOfCircle(r1, r2, x2 - x1, y2 - y1);
  109. }
  110.  
  111. ld IntersectHalfs(int x1, int y1, int r1, int x2, int y2, int r2) {
  112.     return IntersectCircleAndHalfOfCircle(r2, r1, abs(x1 - x2), -abs(y1 - y2));
  113. }
  114.  
  115. ld S(ld r) {
  116.     return r * r * PI;
  117. }
  118.  
  119. int main() {
  120.     ios_base::sync_with_stdio(false);
  121.     cin.tie(nullptr);
  122.     cout.tie(nullptr);
  123.     int x1, y1, x2, y2;
  124.     cin >> x1 >> y1 >> x2 >> y2;
  125.     x2 -= x1;
  126.     y2 -= y1;
  127.     x1 = y1 = 0;
  128.  
  129.     int Afirstx = x1 - 40;
  130.     int Afirsty = y1 + 30;
  131.     int Afirstr = 30;
  132.  
  133.     int Asecondx = x1 + 40;
  134.     int Asecondy = y1 + 30;
  135.     int Asecondr = 30;
  136.  
  137.     int Athirdx = x1;
  138.     int Athirdy = y1 - 20;
  139.     int Athirdr = 60;
  140.  
  141.     int Bfirstx = x2 - 40;
  142.     int Bfirsty = y2 + 30;
  143.     int Bfirstr = 30;
  144.  
  145.     int Bsecondx = x2 + 40;
  146.     int Bsecondy = y2 + 30;
  147.     int Bsecondr = 30;
  148.  
  149.     int Bthirdx = x2;
  150.     int Bthirdy = y2 - 20;
  151.     int Bthirdr = 60;
  152.  
  153.     ld ans = 0;
  154.  
  155.     ans += S(100) + S(100) - IntersectCircles(x1, y1, 100, x2, y2, 100);
  156.     cout << ans << endl;
  157.     ans -= S(Afirstr) - IntersectCircles(Afirstx, Afirsty, Afirstr, x2, y2, 100);
  158.     ans -= S(Asecondr) - IntersectCircles(Asecondx, Asecondy, Asecondr, x2, y2, 100);
  159.     ans -= S(Athirdr) / 2 - IntersectCircleAndHalfOfCircle(x2, y2, 100, Athirdx, Athirdy, Athirdr);
  160.     cout << ans << endl;
  161.     ans -= S(Bfirstr) - IntersectCircles(Bfirstx, Bfirsty, Bfirstr, x1, y1, 100);
  162.     ans -= S(Bsecondr) - IntersectCircles(Bsecondx, Bsecondy, Bsecondr, x1, y1, 100);
  163.     ans -= S(Bthirdr) / 2 - IntersectCircleAndHalfOfCircle(x1, y1, 100, Bthirdx, Bthirdy, Bthirdr);
  164.     cout << ans << endl;
  165.     ans -= IntersectCircles(Afirstx, Afirsty, Afirstr, Bfirstx, Bfirsty, Bfirstr);
  166.     ans -= IntersectCircles(Afirstx, Afirsty, Afirstr, Bsecondx, Bsecondy, Bsecondr);
  167.     ans -= IntersectCircleAndHalfOfCircle(Afirstx, Afirsty, Afirstr, Bthirdx, Bthirdy, Bthirdr);
  168.     cout << ans << endl;
  169.     ans -= IntersectCircles(Asecondx, Asecondy, Asecondr, Bfirstx, Bfirsty, Bfirstr);
  170.     ans -= IntersectCircles(Asecondx, Asecondy, Asecondr, Bsecondx, Bsecondy, Bsecondr);
  171.     ans -= IntersectCircleAndHalfOfCircle(Asecondx, Asecondy, Asecondr, Bthirdx, Bthirdy, Bthirdr);
  172.     cout << ans << endl;
  173.     ans -= IntersectCircleAndHalfOfCircle(Bfirstx, Bfirsty, Bfirstr, Athirdx, Athirdy, Athirdr);
  174.     ans -= IntersectCircleAndHalfOfCircle(Bsecondx, Bsecondy, Bsecondr, Athirdx, Athirdy, Athirdr);
  175.     ans -= IntersectHalfs(Bthirdx, Bthirdy, Bthirdr, Athirdx, Athirdy, Athirdr);
  176.  
  177.     cout << fixed << setprecision(15) << ans << endl;
  178. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement