Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // An AC a day keeps the doctor away. #pragma GCC optimize("Ofast")
- #include <bits/stdc++.h>
- #ifdef local
- #define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
- #define debug(args...) qqbx(#args, args)
- #define orange(args...) danb(#args, args)
- using std::cerr;
- template <typename ...T> void qqbx(const char *s, T ...args) {
- int cnt = sizeof...(T);
- ((cerr << "\e[1;32m(" << s << ") = ("), ..., (cerr << args << (--cnt ? ", " : ")\e[0m\n")));
- }
- template <typename T> void danb(const char *s, T L, T R) {
- cerr << "\e[1;32m[ " << s << " ] = [ ";
- for (int f = 0; L != R; ++L) cerr << (f++ ? ", " : "") << *L;
- cerr << " ]\e[0m\n";
- }
- #else
- #define safe ((void)0)
- #define debug(...) ((void)0)
- #define orange(...) ((void)0)
- #endif // local
- #define all(v) begin(v),end(v)
- using namespace std;
- using ld = long double;
- const ld PI = acos(-1);
- const ld eps = 1e-9;
- using Point = complex<ld>;
- ld cross(Point a, Point b) {
- return imag(conj(a) * b);
- }
- ld dot(Point a, Point b) {
- return real(conj(a) * b);
- }
- ld angle_diff(Point a, Point b) {
- bool neg = (cross(a, b) <= 0);
- ld res = arg(b) - arg(a);
- if (neg) {
- if (res > 0)
- res -= PI * 2;
- return res;
- } else {
- if (res < 0)
- res += PI * 2;
- return res;
- }
- }
- vector<Point> intersect_points(ld R, Point a, Point b) {
- // (o - (a+(b-a)t)) dot (b-a) == 0
- // (o - a) dot (b - a) - norm(b-a) t == 0
- ld d = abs(cross(a, b)) / abs(b-a);
- if (d >= R)
- return {};
- ld s = sqrt(R * R - d * d);
- ld t = dot(-a, b-a) / norm(b-a);
- ld l = t - s / abs(b-a), r = t + s / abs(b-a);
- vector<Point> ans;
- if (0 <= l && l <= 1)
- ans.emplace_back(a + (b-a) * l);
- if (0 <= r && r <= 1)
- ans.emplace_back(a + (b-a) * r);
- return ans;
- }
- ld intersect_area(ld r, Point a, Point b) {
- if (abs(a) >= r && abs(b) >= r) {
- auto ps = intersect_points(r, a, b);
- if (ps.size() < 2) {
- ld theta = angle_diff(a, b);
- return r * r * theta / 2;
- } else {
- assert (ps.size() == 2);
- Point x = ps[0], y = ps[1];
- return r * r * angle_diff(a, x) / 2 + cross(x, y) / 2 + r * r * angle_diff(y, b) / 2;
- }
- }
- if (abs(a) >= r) {
- auto ps = intersect_points(r, a, b);
- if (ps.size() != 1)
- debug(r, a, b);
- assert (ps.size() == 1);
- Point c = ps[0];
- return r * r * angle_diff(a, c) / 2 + cross(c, b) / 2;
- }
- if (abs(b) >= r) {
- auto ps = intersect_points(r, a, b);
- assert (ps.size() == 1);
- Point c = ps[0];
- return cross(a, c) / 2 + r * r * angle_diff(c, b) / 2;
- }
- // (abs(a) <= r && abs(b) <= r)
- return cross(a, b) / 2;
- }
- signed main() {
- ios_base::sync_with_stdio(0), cin.tie(0);
- int n, r;
- cin >> n >> r;
- vector<Point> p(n);
- for (int i = 0; i < n; i++) {
- int x, y;
- cin >> x >> y;
- p[i] = { x, y };
- }
- auto calc = [&p, n, r](Point o) {
- ld area = 0;
- for (int i = 0; i < n; i++)
- area += intersect_area(r, p[i] - o, p[(i+1)%n] - o);
- return area;
- };
- Point o = 0;
- for (int i = 0; i < n; i++) o += p[i];
- o /= n;
- ld step = 0;
- for (int i = 0; i < n; i++)
- step = max(step, abs(p[i] - o));
- step *= 2;
- mt19937 rng;
- ld cur_best = calc(o);
- for (int i = 0; i < 10000; i++) {
- ld theta = uniform_real_distribution<ld>(-PI, PI)(rng);
- ld now = calc(o + polar(step, theta));
- if (now > cur_best) {
- cur_best = now;
- o += polar(step, theta);
- }
- step *= 0.9999;
- }
- debug(step, o);
- // Point o = {1000, 1000};
- cout << fixed << setprecision(10);
- cout << cur_best << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement