Advertisement
AntonGorokhov

Untitled

Oct 6th, 2022
635
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.46 KB | None | 0 0
  1. #ifdef lolipop
  2. #define _GLIBCXX_DEBUG
  3. #endif
  4.  
  5. #include <iostream>
  6. #include <cstddef>
  7. #include <vector>
  8. #include <cstring>
  9. #include <string>
  10. #include <algorithm>
  11. #include <set>
  12. #include <map>
  13. #include <ctime>
  14. #include <unordered_map>
  15. #include <random>
  16. #include <iomanip>
  17. #include <cmath>
  18. #include <queue>
  19. #include <unordered_set>
  20. #include <cassert>
  21. #include <bitset>
  22. #include <deque>
  23. #include <utility>
  24.  
  25. //#define int long long
  26. #define all(x) x.begin(), x.end()
  27. #define rall(x) x.rbegin(), x.rend()
  28. #define ld double
  29.  
  30. using namespace std;
  31.  
  32. inline void fastio() {
  33.     ios_base::sync_with_stdio(false);
  34.     cin.tie(nullptr);
  35.     cout.tie(nullptr);
  36. }
  37.  
  38. struct point {
  39.     point() {}
  40.     point(ld x, ld y): x(x), y(y) {}
  41.     ld x, y;
  42.     void read() {
  43.         cin >> x >> y;
  44.     }
  45. };
  46.  
  47. ld dif(const point& a, const point& b) {
  48.     return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
  49. }
  50.  
  51. ld dist(const point& a, const point& b) {
  52.     return sqrt(dif(a, b));
  53. }
  54.  
  55. struct circle {
  56.     point c;
  57.     ld r;
  58.     circle(point c, ld r): c(c), r(r) {}
  59.     pair<ld, ld> intersect(ld x, bool down = false) {
  60.         if (abs(x - c.x) > r) {
  61.             return {0, -1};
  62.         }
  63.         x -= c.x;
  64.         ld y = sqrt(r * r - x * x);
  65.         if (down) {
  66.             return {c.y - y, c.y};
  67.         }
  68.         return {c.y - y, c.y + y};
  69.     }
  70. };
  71.  
  72. pair<ld, ld> m, l, r, d;
  73.  
  74. vector<pair<ld, ld> > count_smiley(point a, ld x) {
  75.     circle total(a, 100.0);
  76.     circle left(point(a.x - 40, a.y + 30), 30.0);
  77.     circle right(point(a.x + 40, a.y + 30), 30.0);
  78.     circle mouth(point(a.x, a.y - 20), 60.0);
  79.     m = total.intersect(x);
  80.     if (m.first < m.second) {
  81.     } else {
  82.         return {};
  83.     }
  84.     l = left.intersect(x);
  85.     r = right.intersect(x);
  86.     d = mouth.intersect(x, true);
  87.     if (d.first < d.second) {
  88.         // mouth
  89.         if (l.first < l.second) {
  90.             // with left
  91.             return {{m.first, d.first}, {d.second, l.first}, {l.second, m.second}};
  92.         } else {
  93.             if (r.first < r.second) {
  94.                 // with right
  95.                 return {{m.first, d.first}, {d.second, r.first}, {r.second, m.second}};
  96.             } else {
  97.                 // only mouth
  98.                 return {{m.first, d.first}, {d.second, m.second}};
  99.             }
  100.         }
  101.     } else {
  102.         if (l.first < l.second) {
  103.             // with left
  104.             return {{m.first, l.first}, {l.second, m.second}};
  105.         } else {
  106.             // with right
  107.             if (r.first < r.second) {
  108.                 return {{m.first, r.first}, {r.second, m.second}};
  109.             } else {
  110.                 return {m};
  111.             }
  112.         }
  113.     }
  114. }
  115.  
  116. struct event {
  117.     ld y;
  118.     bool open;
  119.     event(ld y, bool open): y(y), open(open) {}
  120.     bool operator < (const event &e) const {
  121.         return y < e.y || (y == e.y && open > e.open);
  122.     }
  123. };
  124.  
  125. vector<event> events;
  126.  
  127. ld count_len(const point& a, const point& b, ld x) {
  128.     auto v1 = count_smiley(a, x), v2 = count_smiley(b, x);
  129.     events.clear();
  130.     for (auto a : v1) {
  131.         events.emplace_back(a.first, true);
  132.         events.emplace_back(a.second, false);
  133.     }
  134.     for (auto a : v2) {
  135.         events.emplace_back(a.first, true);
  136.         events.emplace_back(a.second, false);
  137.     }
  138.     if (events.empty()) {
  139.         return 0;
  140.     }
  141.     sort(all(events));
  142.     ld ans = 0;
  143.     ld now = events[0].y;
  144.     int cnt = 0;
  145.     for (auto event : events) {
  146.         if (event.open) {
  147.             ++cnt;
  148.             if (cnt == 1) {
  149.                 now = event.y;
  150.             }
  151.         } else {
  152.             --cnt;
  153.             if (cnt == 0) {
  154.                 ans += event.y - now;
  155.             }
  156.         }
  157.     }
  158.     return ans;
  159. }
  160.  
  161. int CNT_STEPS = 7e5;
  162.  
  163. void solve() {
  164.     point a, b;
  165.     a.read(), b.read();
  166.     if (dif(a, b) >= 200.0 * 200.0) {
  167.         cout << "40212.3859659494" << '\n';
  168.         return;
  169.     }
  170.     ld min_x = min(a.x, b.x);
  171.     ld max_x = max(a.x, b.x);
  172.     min_x -= 100.0;
  173.     max_x += 100.0;
  174.     ld dx = (max_x - min_x) / (CNT_STEPS + 0.0);
  175.     ld ans = 0.0;
  176.     ld x = min_x + dx / 2.0;
  177.     for (int i = 0; i < CNT_STEPS; ++i) {
  178.         ans += count_len(a, b, x);
  179.         x += dx;
  180.     }
  181.     cout << setprecision(20) << ans * dx << '\n';
  182. }
  183.  
  184. signed main() {
  185. #ifdef lolipop
  186.     freopen("input.txt", "r", stdin);
  187. #else
  188.     fastio();
  189. #endif
  190.     int T = 1;
  191. //    cin >> T;
  192.     while (T--) {
  193.         solve();
  194.     }
  195.     return 0;
  196. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement