Advertisement
999ms

Untitled

Nov 20th, 2019
192
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.49 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define all(x) (x).begin(),(x).end()
  3.  
  4. using namespace std;
  5. using ld = long double;
  6. const ld PI = acosl(-1.0);
  7.  
  8. ld CrossC(ld r1, ld r2, ld dx, ld dy) {
  9.     ld dist = sqrtl(dx * dx + dy * dy);
  10.     if (r1 > r2) swap(r1, r2);
  11.     if (r2 >= dist + r1) return r1 * r1 * PI;
  12.     if (r1 + r2 <= dist) return 0;
  13.     ld a = 2 * acosl((r1 * r1 + dist * dist - r2 * r2) / 2 / r1 / dist);
  14.     ld b = 2 * acosl((r2 * r2 + dist * dist - r1 * r1) / 2 / r2 / dist);
  15.     ld ans = r1 * r1 / 2 * (a - sinl(a)) + r2 * r2 / 2 * (b - sinl(b));
  16.     return ans;
  17. }
  18.  
  19. ld S(ld r, ld h, ld g) {
  20.     assert(h >= 0 && g >= 0);
  21.     assert(h <= r && g <= r);
  22.     ld a = sqrtl(r * r - h * h) - g;
  23.     ld b = sqrtl(r * r - g * g) - h;
  24.     if (a < 0 || b < 0) return 0;
  25.     ld c = sqrtl(a * a + b * b);
  26.     ld ans = a * b / 2;
  27.     ld A = 2 * asinl(c / 2 / r);
  28.     ans += r * r / 2 * (A - sinl(A));
  29.     return ans;
  30. }
  31.  
  32. ld FindS(ld r, ld h, ld g) {
  33.     ld habs = abs(h);
  34.     ld gabs = abs(g);
  35.     ld S1 = S(r, habs, gabs);
  36.     if (h >= 0 && g >= 0) {
  37.         return S1;
  38.     }
  39.     ld kekg = S(r, gabs, 0) * 2;
  40.     ld kekh = S(r, habs, 0) * 2;
  41.     if (h < 0 && g < 0) {
  42.         ld ans = PI * r * r - kekg - kekh + S1;
  43.         return ans;
  44.     } else if (g < 0) {
  45.         return kekh - S1;
  46.     } else {
  47.         return kekg - S1;
  48.     }
  49. }
  50.  
  51. ld CrossCaH(ld X1, ld Y1, ld r1, ld X2, ld Y2, ld r2) {
  52.     ld dx = X2 - X1;
  53.     ld dy = Y2 - Y1;
  54.     dx = abs(dx);
  55.     if (dy + r2 <= 0) return CrossC(r1, r2, dx, dy);
  56.     if (dy - r2 >= 0) return 0;
  57.     if (dx + r2 < -r1) return 0;
  58.     if (dx - r2 > r1) return 0;
  59.     ld xleft, xright;
  60.     {
  61.         ld f = sqrtl(r2 * r2 - dy * dy);
  62.         xleft = dx - f;
  63.         xright = dx + f;
  64.     }
  65.     if (xleft >= -r1 && xright <= r1) {
  66.         auto fy1 = [&] (ld x) {
  67.             return -sqrtl(r1 * r1 - x * x);
  68.         };
  69.         auto fy2 = [&] (ld x) {
  70.             return dy - sqrtl(r2 * r2 - (dx - x) * (dx - x));
  71.         };
  72.         auto f = [&] (ld x) {
  73.             return fy2(x) - fy1(x);
  74.         };
  75.         ld mid1, mid2;
  76.         for (int itr = 0; itr < 200; itr++) {
  77.             mid1 = xleft + (xright - xleft) / 3;
  78.             mid2 = xright - (xright - xleft) / 3;
  79.             if (f(mid1) < f(mid2)) {
  80.                 xright = mid2;
  81.             } else {
  82.                 xleft = mid1;
  83.             }
  84.         }
  85.         if (f(xleft) > 0) {
  86.             return FindS(r2, 0, dy) * 2;
  87.         } else {
  88.             return CrossC(r1, r2, dx, dy) - FindS(r2, 0, -dy) * 2;
  89.         }
  90.     }
  91.     if (xleft <= -r1 && xright >= r1) {
  92.         auto fy1 = [&] (ld x) {
  93.             return sqrtl(r1 * r1 - x * x);
  94.         };
  95.         auto fy2 = [&] (ld x) {
  96.             return dy + sqrtl(r2 * r2 - (dx - x) * (dx - x));
  97.         };
  98.         auto f = [&] (ld x) {
  99.             return fy2(x) - fy1(x);
  100.         };
  101.         xleft = -r1;
  102.         xright = r1;
  103.         ld mid1, mid2;
  104.         for (int itr = 0; itr < 200; itr++) {
  105.             mid1 = xleft + (xright - xleft) / 3;
  106.             mid2 = xright - (xright - xleft) / 3;
  107.             if (f(mid1) <= f(mid2)) {
  108.                 xright = mid2;
  109.             } else {
  110.                 xleft = mid1;
  111.             }
  112.         }
  113.         if (f(xleft) < 0) {
  114.             return PI * r1 * r1 / 2;
  115.         } else {
  116.             return CrossC(r1, r2, dx, dy) - PI * r1 * r1 / 2;
  117.         }
  118.     }
  119.     {
  120.         ld up, down;
  121.         ld xmid;
  122.         {
  123.             // up
  124.             xleft = dx - r2;
  125.             xright = r1;
  126.             auto fy1 = [&] (ld x) {
  127.                 return sqrtl(r1 * r1 - x * x);
  128.             };
  129.             auto fy2 = [&] (ld x) {
  130.                 return dy + sqrtl(r2 * r2 - (dx - x) * (dx - x));
  131.             };
  132.             for (int itr = 0; itr < 200; itr++) {
  133.                 xmid = (xleft + xright) / 2;
  134.                 if (fy1(xmid) < fy2(xmid)) {
  135.                     xright = xmid;
  136.                 } else {
  137.                     xleft = xmid;
  138.                 }
  139.  
  140.             }
  141.             up = xleft;
  142.         }
  143.         {
  144.             // down
  145.             xleft = dx - r2;
  146.             xright = r1;
  147.             auto fy1 = [&] (ld x) {
  148.                 return -sqrtl(r1 * r1 - x * x);
  149.             };
  150.             auto fy2 = [&] (ld x) {
  151.                 return dy - sqrtl(r2 * r2 - (dx - x) * (dx - x));
  152.             };
  153.             for (int itr = 0; itr < 200; itr++) {
  154.                 xmid = (xleft + xright) / 2;
  155.                 if (fy1(xmid) < fy2(xmid)) {
  156.                     xleft = xmid;
  157.                 } else {
  158.                     xright = xmid;
  159.                 }
  160.  
  161.             }
  162.             down = xleft;
  163.         }
  164.         if (up < down) {
  165.             ld ans = FindS(r1, 0, down) + FindS(r2, dy, dx - down);
  166.             return ans;
  167.         } else {
  168.             ld ans = CrossC(r1, r2, dx, dy) - FindS(r1, 0, up) - FindS(r2, -dy, dx - up);
  169.             return ans;
  170.         }
  171.     }
  172.     assert(false);
  173. }
  174.  
  175. ld CrossHaH(ld x1, ld y1, ld x2, ld y2) {
  176.     ld dx = x2 - x1;
  177.     ld dy = y2 - y1;
  178.     dy = abs(dy);
  179.     dx = abs(dx);
  180.     return CrossCaH(0, 0, 60, dx, dy, 60);
  181. }
  182.  
  183. struct Smile {
  184.     ld xmid = 0, ymid = 0;
  185.     ld leftEyeX, leftEyeY = 0;
  186.     ld rightEyeX = 0, rightEyeY = 0;
  187.     ld mouthX = 0, mouthY = 0;
  188.     const ld faceR = 100;
  189.     const ld leftEyeR = 30;
  190.     const ld rightEyeR = 30;
  191.     const ld mouthR = 60;
  192.     Smile(ld xmid, ld ymid) : xmid(xmid), ymid(ymid) {
  193.         leftEyeX = xmid - 40;
  194.         leftEyeY = ymid + 30;
  195.         rightEyeX = xmid + 40;
  196.         rightEyeY = ymid + 30;
  197.         mouthX = xmid;
  198.         mouthY = ymid - 20;
  199.     }
  200. };
  201.  
  202. int main() {
  203.     ld x1, y1, x2, y2;
  204.     cin >> x1 >> y1 >> x2 >> y2;
  205.     Smile a(x1, y1);
  206.     Smile b(x2, y2);
  207.  
  208.     ld ans = 0;
  209.  
  210.     ld dx = x2 - x1;
  211.     ld dy = y2 - y1;
  212.  
  213.     ans += PI * a.faceR * a.faceR + PI * b.faceR * b.faceR - CrossC(a.faceR, b.faceR, dx, dy);
  214.  
  215.     ans -= PI * a.leftEyeR * a.leftEyeR - CrossC(a.leftEyeR, b.faceR, b.xmid - a.leftEyeX, b.ymid - a.leftEyeY);
  216.     ans -= PI * a.rightEyeR * a.rightEyeR - CrossC(a.rightEyeR, b.faceR, b.xmid - a.rightEyeX, b.ymid - a.rightEyeY);
  217.  
  218.     ans -= PI * b.leftEyeR * b.leftEyeR - CrossC(b.leftEyeR, a.faceR, a.xmid - b.leftEyeX, a.ymid - b.leftEyeY);
  219.     ans -= PI * b.rightEyeR * b.rightEyeR - CrossC(b.rightEyeR, a.faceR, a.xmid - b.rightEyeX, a.ymid - b.rightEyeY);
  220.  
  221.     ld cur1 = CrossCaH(a.mouthX, a.mouthY, a.mouthR, b.xmid, b.ymid, b.faceR);
  222.     ld cur2 = CrossCaH(b.mouthX, b.mouthY, b.mouthR, a.xmid, a.ymid, a.faceR);
  223.  
  224.     cur1 = 0.5 * PI * a.mouthR * a.mouthR - cur1;
  225.     cur2 = 0.5 * PI * b.mouthR * b.mouthR - cur2;
  226.  
  227.     ans -= cur1 + cur2;
  228.  
  229.     ans -= CrossC(a.leftEyeR, b.leftEyeR, a.leftEyeX - b.leftEyeX, a.leftEyeY - b.leftEyeY);
  230.     ans -= CrossC(a.leftEyeR, b.rightEyeR, a.leftEyeX - b.rightEyeX, a.leftEyeY - b.rightEyeY);
  231.  
  232.     ans -= CrossC(a.rightEyeR, b.leftEyeR, a.rightEyeX - b.leftEyeX, a.rightEyeY - b.leftEyeY);
  233.     ans -= CrossC(a.rightEyeR, b.rightEyeR, a.rightEyeX - b.rightEyeX, a.rightEyeY - b.rightEyeY);
  234.  
  235.     ans -= CrossCaH(a.mouthX, a.mouthY, a.mouthR, b.leftEyeX, b.leftEyeY, b.leftEyeR);
  236.     ans -= CrossCaH(a.mouthX, a.mouthY, a.mouthR, b.rightEyeX, b.rightEyeY, b.rightEyeR);
  237.  
  238.     ans -= CrossCaH(b.mouthX, b.mouthY, b.mouthR, a.leftEyeX, a.leftEyeY, a.leftEyeR);
  239.  
  240.     ans -= CrossCaH(b.mouthX, b.mouthY, b.mouthR, a.rightEyeX, a.rightEyeY, a.rightEyeR);
  241.  
  242.     ld mm = CrossHaH(a.mouthX, a.mouthY, b.mouthX, b.mouthY);
  243.     ans -= mm;
  244.  
  245.     cout << fixed << setprecision(15) << ans << '\n';
  246. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement