Advertisement
bingxuan9112

Untitled

Sep 12th, 2021
664
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.87 KB | None | 0 0
  1. // An AC a day keeps the doctor away.  #pragma GCC optimize("Ofast")
  2. #include <bits/stdc++.h>
  3. #ifdef local
  4. #define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
  5. #define debug(args...) qqbx(#args, args)
  6. #define orange(args...) danb(#args, args)
  7. using std::cerr;
  8. template <typename ...T> void qqbx(const char *s, T ...args) {
  9.     int cnt = sizeof...(T);
  10.     ((cerr << "\e[1;32m(" << s << ") = ("), ..., (cerr << args << (--cnt ? ", " : ")\e[0m\n")));
  11. }
  12. template <typename T> void danb(const char *s, T L, T R) {
  13.     cerr << "\e[1;32m[ " << s << " ] = [ ";
  14.     for (int f = 0; L != R; ++L) cerr << (f++ ? ", " : "") << *L;
  15.     cerr << " ]\e[0m\n";
  16. }
  17. #else
  18. #define safe ((void)0)
  19. #define debug(...) ((void)0)
  20. #define orange(...) ((void)0)
  21. #endif // local
  22. #define all(v) begin(v),end(v)
  23.  
  24. using namespace std;
  25. using ld = long double;
  26. const ld PI = acos(-1);
  27. const ld eps = 1e-9;
  28.  
  29. using Point = complex<ld>;
  30.  
  31. ld cross(Point a, Point b) {
  32.     return imag(conj(a) * b);
  33. }
  34. ld dot(Point a, Point b) {
  35.     return real(conj(a) * b);
  36. }
  37. ld angle_diff(Point a, Point b) {
  38.     bool neg = (cross(a, b) <= 0);
  39.     ld res = arg(b) - arg(a);
  40.     if (neg) {
  41.         if (res > 0)
  42.             res -= PI * 2;
  43.         return res;
  44.     } else {
  45.         if (res < 0)
  46.             res += PI * 2;
  47.         return res;
  48.     }
  49. }
  50.  
  51. vector<Point> intersect_points(ld R, Point a, Point b) {
  52.     // (o - (a+(b-a)t)) dot (b-a) == 0
  53.     // (o - a) dot (b - a) - norm(b-a) t == 0
  54.     ld d = abs(cross(a, b)) / abs(b-a);
  55.     if (d >= R)
  56.         return {};
  57.     ld s = sqrt(R * R - d * d);
  58.     ld t = dot(-a, b-a) / norm(b-a);
  59.     ld l = t - s / abs(b-a), r = t + s / abs(b-a);
  60.     vector<Point> ans;
  61.     if (0 <= l && l <= 1)
  62.         ans.emplace_back(a + (b-a) * l);
  63.     if (0 <= r && r <= 1)
  64.         ans.emplace_back(a + (b-a) * r);
  65.     return ans;
  66. }
  67. ld intersect_area(ld r, Point a, Point b) {
  68.     if (abs(a) >= r && abs(b) >= r) {
  69.         auto ps = intersect_points(r, a, b);
  70.         if (ps.size() < 2) {
  71.             ld theta = angle_diff(a, b);
  72.             return r * r * theta / 2;
  73.         } else {
  74.             assert (ps.size() == 2);
  75.             Point x = ps[0], y = ps[1];
  76.             return r * r * angle_diff(a, x) / 2 + cross(x, y) / 2 + r * r * angle_diff(y, b) / 2;
  77.         }
  78.     }
  79.     if (abs(a) >= r) {
  80.         auto ps = intersect_points(r, a, b);
  81.         if (ps.size() != 1)
  82.             debug(r, a, b);
  83.         assert (ps.size() == 1);
  84.         Point c = ps[0];
  85.         return r * r * angle_diff(a, c) / 2 + cross(c, b) / 2;
  86.     }
  87.     if (abs(b) >= r) {
  88.         auto ps = intersect_points(r, a, b);
  89.         assert (ps.size() == 1);
  90.         Point c = ps[0];
  91.         return cross(a, c) / 2 + r * r * angle_diff(c, b) / 2;
  92.     }
  93.     // (abs(a) <= r && abs(b) <= r)
  94.     return cross(a, b) / 2;
  95. }
  96.  
  97. signed main() {
  98.     ios_base::sync_with_stdio(0), cin.tie(0);
  99.     int n, r;
  100.     cin >> n >> r;
  101.     vector<Point> p(n);
  102.     for (int i = 0; i < n; i++) {
  103.         int x, y;
  104.         cin >> x >> y;
  105.         p[i] = { x, y };
  106.     }
  107.  
  108.     auto calc = [&p, n, r](Point o) {
  109.         ld area = 0;
  110.         for (int i = 0; i < n; i++)
  111.             area += intersect_area(r, p[i] - o, p[(i+1)%n] - o);
  112.         return area;
  113.     };
  114.     Point o = 0;
  115.     for (int i = 0; i < n; i++) o += p[i];
  116.     o /= n;
  117.  
  118.     ld step = 0;
  119.     for (int i = 0; i < n; i++)
  120.         step = max(step, abs(p[i] - o));
  121.     step *= 2;
  122.     mt19937 rng;
  123.  
  124.     ld cur_best = calc(o);
  125.     for (int i = 0; i < 10000; i++) {
  126.         ld theta = uniform_real_distribution<ld>(-PI, PI)(rng);
  127.         ld now = calc(o + polar(step, theta));
  128.         if (now > cur_best) {
  129.             cur_best = now;
  130.             o += polar(step, theta);
  131.         }
  132.         step *= 0.9999;
  133.     }
  134.     debug(step, o);
  135.     // Point o = {1000, 1000};
  136.     cout << fixed << setprecision(10);
  137.     cout << cur_best << '\n';
  138. }
  139.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement