API tools faq
paste
Advertisement
999ms

Untitled

999ms
Nov 20th, 2019
211
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 13.74 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. const double M__PI = 3.1415926535897932384626433832795;
  8.  
  9. struct pt
  10. {
  11.     double x, y;
  12.     pt(double x = 0, double y = 0):x(x), y(y){}
  13.     friend pt operator - (pt a, pt b)
  14.     {
  15.         a.x = a.x - b.x;
  16.         a.y = a.y - b.y;
  17.         return a;
  18.     }
  19.     friend pt operator + (pt a, pt b)
  20.     {
  21.         a.x = a.x + b.x;
  22.         a.y = a.y + b.y;
  23.         return a;
  24.     }
  25.     friend pt operator * (pt a, double k)
  26.     {
  27.         a.x = a.x * k;
  28.         a.y = a.y * k;
  29.         return a;
  30.     }
  31. };
  32.  
  33. double RR(pt a)
  34. {
  35.     return a.x * a.x + a.y * a.y;
  36. }
  37.  
  38. pt rot(pt a, double u)
  39. {
  40.     pt res;
  41.     res.x = a.x * cos(u) - a.y * sin(u);
  42.     res.y = a.x * sin(u) + a.y * cos(u);
  43.     return res;
  44. }
  45.  
  46. struct circle
  47. {
  48.     pt a;
  49.     double r;
  50.     bool big;
  51.     double Y;
  52.     circle(pt a = 0, double r = 0, bool big = true, double Y = 1000.0):a(a), r(r), big(big), Y(Y){}
  53. };
  54.  
  55. const double eps = 1e-7;
  56.  
  57. vector<pt> circle_circle(pt a, double r, pt b, double r1)
  58. {
  59.     if (RR(a - b) < eps)
  60.         return vector<pt>();
  61.     if (RR(a -  b) >= (r + r1) * (r + r1) - eps || RR(a -  b) <= (r - r1) * (r - r1) + eps)
  62.         return vector<pt>();
  63.     pt v = b - a;
  64.     double cosu = (r * r + RR(v) - r1 * r1) / (2.0 * sqrt(RR(v)) * r);
  65.     v = v  * (r/ sqrt(RR(v)));
  66.     vector<pt> res;
  67.     res.push_back(a + rot(v, acos(cosu)));
  68.     res.push_back(a + rot(v, -acos(cosu)));
  69.     return res;
  70. }
  71.  
  72. pt fromangle(circle a, double u)
  73. {
  74.     return a.a + pt(cos(u), sin(u)) * a.r;
  75. }
  76. double toangle(circle a, pt p)
  77. {
  78.     double u =  atan2(p.y - a.a.y, p.x - a.a.x);
  79.     if (u < 0)
  80.         u = u + M__PI * 2.0;
  81.     return u;
  82. }
  83.  
  84. double vc(pt a, pt b)
  85. {
  86.     return a.x * b.y - a.y * b.x;
  87. }
  88. int sign(double p)
  89. {
  90.     if (fabs(p) < eps)
  91.         return 0;
  92.     if (p < eps)
  93.         return -1;
  94.     return 1;
  95. }
  96.  
  97. void addPt(circle a, double y, vector<pt> &p)
  98. {
  99.     if (fabs(a.a.y - y) >= a.r - eps)
  100.         return;
  101.     double d = sqrt(a.r * a.r - (a.a.y - y) * (a.a.y - y));
  102.     pt res(a.a.x, y);
  103.     p.push_back(res + pt(d));
  104.     p.push_back(res - pt(d));
  105. }
  106.  
  107. bool check_pt_in_circle(circle a, pt b)
  108. {
  109.     return RR(a.a - b) <= a.r * a.r + eps;
  110. }
  111.  
  112. bool check(circle a, circle b, double y, pt p)
  113. {
  114.     if (check_pt_in_circle(b, p) &&  check_pt_in_circle(a, p) && p.y <= y + eps)
  115.         return true;
  116.     return false;
  117. }
  118.  
  119. double bestU(double uf, double us)//  ���� ������� ����
  120. {
  121.     if (uf < us)
  122.         return (uf + us) / 2.0;
  123.     return (uf + us + 2.0 * M__PI) / 2.0;
  124. }
  125.  
  126. bool highU(double uf, double us, circle a, double y) // ��������� ��� ����� ������� ����� ������ � �������
  127. {
  128.     if (uf < us)
  129.     {
  130.         if (uf < M__PI / 2.0 && us > M__PI / 2.0)
  131.             return a.a.y + a.r <= y + eps;
  132.     }
  133.     else
  134.     {
  135.         swap(uf, us);
  136.         if (!(uf < M__PI / 2.0 && us > M__PI / 2.0))
  137.             return a.a.y + a.r <= y + eps;
  138.     }
  139.     return true;
  140. }
  141.  
  142. double distU(double u1, double u2)
  143. {
  144.     if (u1 < u2)
  145.         return u2 - u1;
  146.     return u2 + 2.0 * M__PI - u1;
  147. }
  148.  
  149. double S_sector(pt f, pt s, circle a)// ���� ������� �������
  150. {
  151.     double S = fabs(vc(f - a.a, s - a.a)) / 2;
  152.     double u1 = toangle(a, f);
  153.     double u2 = toangle(a, s);
  154.     double u = distU(u1, u2);
  155.     //cout << u1 << " " << u2 << " u = "<< u << endl;
  156.     double res = min(u, (2.0 * M__PI - u)) * a.r * a.r / 2.0 - S;
  157.     //cout << res << endl;
  158.     if (u > 2.0 * M__PI - u)
  159.         res =  M__PI * a.r * a.r  - res;
  160.     return res;
  161. }
  162.  
  163. double sector(pt f, pt s, circle a, circle b, double y, vector<pt> &P) // ��������� ������������ ���� c f �� s �� ���������� a  � ���������� �������, ���� ���������
  164. {
  165.    // cout << "sector " << endl;
  166.     if (fabs(RR(a.a - f) - a.r * a.r) >= eps || fabs(RR(a.a - s) - a.r * a.r) >= eps)// ���� ����� �� ���� �� ���������, �� ����� �� �� ������
  167.         return 0.0;
  168.    //  cout << ":)" << endl;
  169.     //cout << "   " << f.x << " " << f.y << " " << s.x << " " << s.y << " " << a.r << endl;
  170.     double u1 = toangle(a, f);
  171.     double u2 = toangle(a, s);
  172.     //cout << u1 << " " << u2 << endl;
  173.     for (int i = 0; i < P.size(); ++i)
  174.     {
  175.         double u = toangle(a, P[i]);
  176.         if (fabs(RR(a.a - P[i]) - a.r * a.r) > eps )
  177.             continue;
  178.         if (u1 < u2 && fabs(u - u1) > eps && fabs(u - u2) > eps  && u > u1 + eps && u < u2 - eps)
  179.             return 0.0;
  180.         if (u1 > u2 && fabs(u - u1) > eps && fabs(u - u2) > eps && !(u > u2 + eps && u < u1 - eps))
  181.             return 0.0;
  182.     }
  183.    // cout << ":))" << endl;
  184.  
  185.     double u = bestU(u1, u2);
  186.     pt p = fromangle(a, u);
  187.    // cout << p.x << " " << p.y << endl;
  188.    // cout <<  highU(u1, u2, a, y) << " " << u1 << " " << u2  << endl;
  189.     //cout << f.x << " " << f.y << " " << s.x << " " << s.y << " " << a.a.x << " " << a.a.y << " " <<  u << " " << u1 << endl;
  190.     if (check(a, b, y, p) && highU(u1, u2, a, y))// ���� �� ���� ����� ����� �� ���� 3 � ����� ������� ���� y
  191.     {
  192.        // cout << f.x << " " << f.y << " " << s.x << " " << s.y << " " << a.a.x << " " << a.a.y << " " <<  u << " " << u1 << endl;
  193.        // cout << S_sector(f, s, a) << endl;
  194.         return S_sector(f, s, a);
  195.     }
  196.     return 0.0;
  197. }
  198.  
  199. double answ(circle a, circle b, double y, pt f, pt s, vector<pt> &P)
  200. {
  201.     //if (fabs(f.y - y) < eps && fabs(s.y - y) < eps) // ��� �������� ��� ������� �� ���� �� ������� ������
  202.      //   return 0.0;
  203.     // cout << "answ: " << f.x << " " << f.y << " " << s.x << " " << s.y << endl;
  204.     if (RR(a.a - b.a) < eps && fabs(a.r - b.r) < eps)
  205.         return sector(f, s, a, b, y, P) + sector(s, f, a, b, y, P);
  206.     return sector(f, s, a, b, y, P) + sector(s, f, a, b, y, P) + sector(f, s, b, a, y, P) + sector(s, f, b, a, y, P);
  207.  
  208. }
  209.  
  210. double S(circle a, circle b, double y = 1000.0)// ���������� ������� ����������� 2 �����������, � ������������� y <= const
  211. {
  212.   // cout << "input:  "<< a.a.x << " " << a.a.y << " " << a.r << " " << b.a.x << " " << b.a.y << " "<< b.r << "  " << y << endl;
  213. // ������� ��� ����� ����������
  214.     vector<pt> p = circle_circle(a.a, a.r, b.a, b.r);
  215.     addPt(a, y, p);
  216.     addPt(b, y, p);
  217.   //  for (int i = 0; i < p.size(); ++i)
  218.   //      cout << p[i].x << " " << p[i].y << endl;
  219.   //  cout << endl;
  220.     //cout << p.size() << endl;
  221. // ������� ������� � �� ������� �� �� ���� 3 ��������
  222.     vector<pt> A;
  223.     for (int i = 0; i < p.size(); ++i)
  224.     {
  225.         if (check(a, b, y, p[i]))
  226.         {
  227.            // cout << "+" << endl;
  228.             bool t = true;
  229.             for (int i1 = 0; i1 < A.size(); ++i1)
  230.             {
  231.                 if (RR(A[i1] - p[i]) < eps)
  232.                     t = false;
  233.             }
  234.             if (t)
  235.                 A.push_back(p[i]);
  236.         }
  237.     }
  238.  
  239.     //cout << A.size() << endl;
  240.  
  241.     // ���� ������ ������ �� �����, �� ���� ���� ������ ������ ���� 0
  242.     if (A.size() == 0)
  243.     {
  244.         //cout << "O_O" << endl;
  245.         if (RR(a.a - b.a) < (a.r + b.r) * (a.r + b.r) && a.a.y <= y + eps && b.a.y <= y + eps)
  246.             return M__PI * min(a.r, b.r) * min(a.r, b.r);
  247.         return 0.0;
  248.     }
  249.  
  250.     // ���� 4 �� ����������� � ������� �������� ��������
  251.     if (A.size() == 4)// ��������� � ������� ������
  252.     {
  253.         vector<pt> ans;
  254.         for (int i = 0; i < A.size(); ++i)
  255.         {
  256.             for (int i1 = i + 1; i1 < A.size(); ++i1)
  257.             {
  258.                 vector<pt> p;
  259.                 for (int j = 0; j < A.size(); ++j)
  260.                     if (j != i && j !=i1)
  261.                         p.push_back(A[j]);
  262.                 int s = sign(vc(A[i1] - A[i], p[0] - A[i])) * sign(vc(A[i1] - A[i], p[1] - A[i]));
  263.                 if (s < 0)// ������ ���������
  264.                 {
  265.                     ans.clear();
  266.                     ans.push_back(A[i]);
  267.                     ans.push_back(p[0]);
  268.                     ans.push_back(A[i1]);
  269.                     ans.push_back(p[1]);
  270.                 }
  271.             }
  272.         }
  273.         A = ans;
  274.         //if (A.size()!= 4)
  275.         //    cout << "O_O" << endl;
  276.     }
  277.  
  278.     // ������ 4 ���� �� �����
  279.     if (A.size() > 4)
  280.     {
  281.         while(true)
  282.         {
  283.             cout <<"O_O" << endl;
  284.         }
  285.     }
  286.     if (A.size() == 1)
  287.     {
  288.        // cout << "O_i" << endl;
  289.         return 0;
  290.     }
  291.  
  292.  
  293.     //cout << "A:" << A.size() << endl;
  294.     //for (int i = 0; i < A.size(); ++i)
  295.     //  cout << A[i].x << " " << A[i].y << endl;
  296.     //cout << endl;
  297.  
  298.     if (A.size() == 2)
  299.     {
  300.         return  answ(a, b, y, A[0], A[1], A);
  301.     }
  302.  
  303.     double ans = 0;
  304.     for (int i = 0; i < A.size(); ++i)
  305.     {
  306.         double q = answ(a, b, y, A[i], A[(i + 1) % A.size()], A);
  307.         ans += q; // ���������� ������� �� ������ �� ���������
  308.         ans += fabs(vc(A[i] - A[0], A[(i + 1) % A.size()] - A[0])) / 2.0; // ���������� ��������� �������
  309.        // cout <<  fabs(vc(A[i] - A[0], A[(i + 1) % A.size()] - A[0])) / 2.0 << endl;
  310.        //cout << q << endl;
  311.     }
  312.  
  313.     return ans;
  314.  
  315. }
  316.  
  317. double Sstupid(circle a, circle b, double y1 = 1000.0)// ���������� ������� ����������� 2 �����������, � ������������� y <= const
  318. {
  319.     double ans = 0.0;
  320.     for (double x = -300.0; x < 300.0; x += 0.1)
  321.     {
  322.         for (double y = -300.0; y < 300.0; y += 0.1)
  323.         {
  324.            if (check(a, b, y1, pt(x, y)))
  325.              ans += 1e-2;
  326.         }
  327.     }
  328.     return ans;
  329. }
  330.  
  331. vector<circle> smile;
  332.  
  333.  
  334. void input(pt a)
  335. {
  336.     smile.push_back(circle(pt(a.x      , a.y      ), 100.0, 1));
  337.     smile.push_back(circle(pt(a.x - 40.0, a.y + 30.0), 30.0 , 0));
  338.     smile.push_back(circle(pt(a.x + 40.0, a.y + 30.0), 30.0 , 0));
  339.     smile.push_back(circle(pt(a.x      , a.y - 20.0), 60.0 , 0, a.y - 20.0));
  340. }
  341.  
  342. double Ss(circle a)
  343. {
  344.     //cout << a.Y << " " << a.r << " " << a.a.y << endl;
  345.     if (a.Y > 998.0)
  346.         return a.r * a.r * M__PI;
  347.     else
  348.         return a.r * a.r * M__PI / 2.0;
  349. }
  350.  
  351. bool checkS(vector<circle> &A, pt p)
  352. {
  353.     for (int i = 0; i <  A.size(); ++i)
  354.     {
  355.         bool in = false;
  356.         if (RR(A[i].a - p) <= A[i].r * A[i].r && A[i].Y >= p.y)
  357.             in = true;
  358.         if (in && !A[i].big)
  359.             return false;
  360.         if (!in && A[i].big)
  361.             return false;
  362.     }
  363.     return true;
  364. }
  365.  
  366. double superStupid(vector<circle> A, vector<circle> B)
  367. {
  368.     double ans = 0.0;
  369.     for (double x = -300.0; x <= 300.0; x += 0.1)
  370.     {
  371.         for (double y = -300.0; y <= 300.0; y += 0.1)
  372.         {
  373.            if (checkS(A, pt(x, y)) ||  checkS(B, pt(x, y)))
  374.              ans += 1e-2;
  375.         }
  376.     }
  377.     return ans;
  378. }
  379.  
  380.  
  381. int main()
  382. {
  383.     /*circle A1, B1;
  384.     cin >> A1.a.x >> A1.a.y >> A1.r;
  385.     cin >> B1.a.x >> B1.a.y >> B1.r;
  386.     double y;
  387.     cin >> y;
  388.     cout << S(A1, B1, y) << " " << Sstupid(A1, B1, y) << endl;
  389.     return 0;*/
  390.     pt a, b;
  391.     cin >> a.x >> a.y;
  392.     cin >> b.x >> b.y;
  393.  
  394.     input(a);
  395.     input(b);
  396.  
  397.     double ans = 0;
  398.     double stupid_ans = 0;
  399.     for (int i = 0; i < smile.size(); ++i)
  400.     {
  401.         if (smile[i].big == 1)
  402.             ans += Ss(smile[i]);
  403.         else
  404.             ans -= Ss(smile[i]);
  405.        // cout << ans << endl;
  406.     }
  407.     /*if (RR(a - b) < eps)
  408.     {
  409.         cout.precision(10);
  410.          cout << fixed<< ans / 2.0 << endl;
  411.          return 0;}
  412.     */
  413.  
  414.     vector<circle> A, B;
  415.     for (int i = 0; i < smile.size() / 2; ++i)
  416.     {
  417.         A.push_back(smile[i]);
  418.         B.push_back(smile[smile.size() / 2 + i]);
  419.         for (int i1 =  smile.size() / 2; i1 < smile.size(); ++i1)
  420.         {
  421.             double p = -1.0;
  422.             if (smile[i].big != smile[i1].big)
  423.                 p = 1.0;
  424.             ans += p * S(smile[i], smile[i1], min(smile[i].Y, smile[i1].Y));
  425.            // stupid_ans += Sstupid(smile[i], smile[i1], min(smile[i].Y, smile[i1].Y));
  426.             double tt = min(smile[i].r * smile[i].r, smile[i1].r * smile[i1].r) * M__PI;
  427.             //cout << S(smile[i], smile[i1], min(smile[i].Y, smile[i1].Y)) << " " << Sstupid(smile[i], smile[i1], min(smile[i].Y, smile[i1].Y)) << endl;
  428. //          system ("pause");
  429.             //<< " " << min(smile[i].r * smile[i].r, smile[i1].r * smile[i1].r) * M__PI<< endl;; //<< " " << Sstupid(smile[i], smile[i1], min(smile[i].Y, smile[i1].Y)) << endl;
  430.             //int p1;
  431.             //cout << "go" << endl;
  432.             //cin >> p1;
  433.         }
  434.     }
  435.     //cout << superStupid(A, B) <<endl;
  436.     //for (int i = 0; i < B.size(); ++i)
  437.     //    cout << B[i].a.x << " " << B[i].a.y << B[i].r << endl;
  438.  
  439.     cout.precision(10);
  440.     cout << fixed;
  441.     cout << ans << endl;
  442.  
  443.     return 0;
  444. }
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!