QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#367530#8513. Insects, Mathematics, Accuracy, and Efficiencyhos_lyricTL 1ms4136kbC++146.9kb2024-03-26 05:14:082024-03-26 05:14:08

Judging History

你现在查看的是最新测评结果

  • [2024-03-26 05:14:08]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4136kb
  • [2024-03-26 05:14:08]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


using Double = long double;
const Double EPS = 1e-10L;
const Double INF = 1e+10L;
const Double PI = acos(-1.0L);
inline int sig(Double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
inline Double sq(Double r) { return r * r; }

struct Pt {
  Double x, y;
  Pt() {}
  Pt(Double x_, Double y_) : x(x_), y(y_) {}
  Pt operator+(const Pt &a) const { return Pt(x + a.x, y + a.y); }
  Pt operator-(const Pt &a) const { return Pt(x - a.x, y - a.y); }
  Pt operator*(const Pt &a) const { return Pt(x * a.x - y * a.y, x * a.y + y * a.x); }
  Pt operator/(const Pt &a) const { const Double d2 = a.abs2(); return Pt((x * a.x + y * a.y) / d2, (y * a.x - x * a.y) / d2); }
  Pt operator+() const { return Pt(+x, +y); }
  Pt operator-() const { return Pt(-x, -y); }
  Pt operator*(const Double &k) const { return Pt(x * k, y * k); }
  Pt operator/(const Double &k) const { return Pt(x / k, y / k); }
  friend Pt operator*(const Double &k, const Pt &a) { return Pt(k * a.x, k * a.y); }
  Pt &operator+=(const Pt &a) { x += a.x; y += a.y; return *this; }
  Pt &operator-=(const Pt &a) { x -= a.x; y -= a.y; return *this; }
  Pt &operator*=(const Pt &a) { return *this = *this * a; }
  Pt &operator/=(const Pt &a) { return *this = *this / a; }
  Pt &operator*=(const Double &k) { x *= k; y *= k; return *this; }
  Pt &operator/=(const Double &k) { x /= k; y /= k; return *this; }
  Double abs() const { return sqrt(x * x + y * y); }
  Double abs2() const { return x * x + y * y; }
  Double arg() const { return atan2(y, x); }
  Double dot(const Pt &a) const { return x * a.x + y * a.y; }
  Double det(const Pt &a) const { return x * a.y - y * a.x; }
  friend ostream &operator<<(ostream &os, const Pt &a) { os << "(" << a.x << ", " << a.y << ")"; return os; }
  bool operator<(const Pt &a) const { return (x != a.x) ? (x < a.x) : (y < a.y); }
};
inline Double tri(const Pt &a, const Pt &b, const Pt &c) { return (b - a).det(c - a); }

Pt proj(const Pt &a, const Pt &b) { return a * a.dot(b) / a.abs2(); }
Pt perp(const Pt &a, const Pt &b, const Pt &c) { return a + proj(b - a, c - a); }
Pt refl(const Pt &a, const Pt &b, const Pt &c) { return perp(a, b, c) * 2 - c; }

vector<Pt> convexHull(vector<Pt> ps) {
  const int n = ps.size();
  sort(ps.begin(), ps.end());
  vector<Pt> qs;
  for (int i = 0; i < n; qs.push_back(ps[i++]))
    for (; qs.size() > 1 && sig(tri(qs[qs.size() - 2], qs[qs.size() - 1], ps[i])) <= 0; qs.pop_back()) {}
  const int r = qs.size();
  for (int i = (int)ps.size() - 2; i >= 0; qs.push_back(ps[i--]))
    for (; (int)qs.size() > r && sig(tri(qs[qs.size() - 2], qs[qs.size() - 1], ps[i])) <= 0; qs.pop_back()) {}
  if (qs.size() > 1) qs.pop_back();
  return qs;
}

vector<Pt> pCL(const Pt &a, Double r, const Pt &b, const Pt &c) {
  const Pt h = perp(b, c, a);
  const Double d = (h - a).abs();
  if (sig(d - r) <= 0) {
    const Double y = sqrt(max(r * r - d * d, (Double)0));
    const Pt e = (c - b) / (c - b).abs();
    return { h - e * y, h + e * y };
  } else {
    return {};
  }
}


Double mod(Double t) {
  for (; t < 1; t += 2 * PI) {}
  for (; t >= 1 + 2 * PI; t -= 2 * PI) {}
  return t;
}

int N;
Double R;
vector<Pt> P;

Pt cir(Double t) {
  return Pt(R * cos(t), R * sin(t));
}

int main() {
  for (; ~scanf("%d%Lf", &N, &R); ) {
    P.resize(N);
    for (int i = 0; i < N; ++i) {
      int x, y;
      scanf("%d%d", &x, &y);
      P[i] = Pt(x, y);
    }
    
    P = convexHull(P);
    N = P.size();
// cerr<<"P = "<<P<<endl;
    
    vector<Double> sums(N + 1, 0.0);
    for (int i = 0; i < N; ++i) {
      sums[i + 1] = sums[i] + P[i].det(P[(i + 1) % N]);
    }
    Double ans = sums[N];
    if (N >= 2) {
      vector<int> ini(N, 0);
      vector<Double> ts{1, 1 + 2 * PI};
      for (int i = 0; i < N; ++i) {
        const auto res = pCL(Pt(0, 0), R, P[i], P[(i + 1) % N]);
        assert(res.size() == 2);
        const Double t0 = mod(res[0].arg());
        const Double t1 = mod(res[1].arg());
// cerr<<res<<" "<<t0<<" "<<t1<<endl;
        if (t0 > t1) {
          ini[i] = 1;
        }
        ts.push_back(t0);
        ts.push_back(t1);
      }
      sort(ts.begin(), ts.end());
// cerr<<"ini = "<<ini<<endl;
// cerr<<"ts = "<<ts<<endl;
      
      // visible: edges [l, r)
      int l = 0, r = 0;
      for (int i = 1; i < N; ++i) {
        if (!ini[i - 1] && ini[i]) l = i;
        if (ini[i - 1] && !ini[i]) r = i;
      }
      for (int h = 0; h < (int)ts.size() - 1; ++h) {
        const Double t0 = ts[h];
        const Double t1 = ts[h + 1];
        const Double tMid = (t0 + t1) / 2;
        const Pt p = cir(tMid);
        for (; tri(P[l], P[(l + 1) % N], p) > 0; l = (l + 1) % N) {}
        for (; tri(P[r], P[(r + 1) % N], p) < 0; r = (r + 1) % N) {}
// cerr<<"["<<t0<<", "<<t1<<"] "<<p<<" ["<<l<<", "<<r<<")"<<endl;
        Double mx = 0.0;
        chmax(mx, tri(P[r], P[l], cir(t0)));
        chmax(mx, tri(P[r], P[l], cir(t1)));
        // parallel to P[l]P[r]
        Double t2 = mod((P[r] - P[l]).arg() - PI / 2);
        for (int s = -1; s <= +1; ++s) {
          const Double t = t2 + s * PI;
          if (t0 <= t && t <= t1) {
// cerr<<"  t = "<<t<<", cir(t) = "<<cir(t)<<endl;
            chmax(mx, tri(P[r], P[l], cir(t)));
          }
        }
        Double here = sums[N];
        if (l < r) {
          here -= (sums[r] - sums[l]);
        } else {
          here -= (sums[r] + (sums[N] - sums[l]));
        }
        here += P[l].det(P[r]);
        here += mx;
// cerr<<"  mx = "<<mx<<", here = "<<here<<endl;
        chmax(ans, here);
      }
      
    }
    ans /= 2;
    printf("%.12Lf\n", ans);
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4136kb

input:

4 1000
-1000 0
0 0
1000 0
0 -1000

output:

2000000.000000000000

result:

ok found '2000000.000000000', expected '2000000.000000000', error '0.000000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

2 100
17 7
19 90

output:

4849.704644437564

result:

ok found '4849.704644438', expected '4849.704644438', error '0.000000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 4112kb

input:

1 100
13 37

output:

0.000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 4080kb

input:

4 1000
-800 600
800 600
-800 -600
800 -600

output:

2240000.000000000000

result:

ok found '2240000.000000000', expected '2240000.000000000', error '0.000000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 4076kb

input:

3 1000
200 400
-600 -400
400 -800

output:

1045685.424949238020

result:

ok found '1045685.424949238', expected '1045685.424949238', error '0.000000000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

4 1000
200 -600
600 -400
800 -600
0 -800

output:

732310.562561766055

result:

ok found '732310.562561766', expected '732310.562561766', error '0.000000000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3896kb

input:

4 1000
-600 700
-300 900
0 800
-800 400

output:

892213.595499957939

result:

ok found '892213.595499958', expected '892213.595499958', error '0.000000000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

5 1000
-300 -200
-200 -400
-100 -700
-800 -500
-500 -300

output:

619005.494464025914

result:

ok found '619005.494464026', expected '619005.494464026', error '0.000000000'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3908kb

input:

1000 10000
-9998 -136
-9996 -245
-9995 -280
-9993 -347
-9991 -397
-9989 -440
-9985 -525
-9984 -545
-9983 -564
-9981 -599
-9979 -632
-9973 -721
-9971 -747
-9966 -810
-9963 -846
-9957 -916
-9953 -958
-9948 -1008
-9945 -1037
-9938 -1103
-9927 -1196
-9920 -1253
-9913 -1308
-9908 -1346
-9891 -1465
-9874 ...

output:

314026591.780110353837

result:

ok found '314026591.780110359', expected '314026591.780110359', error '0.000000000'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

2 10000
-9999 0
-9998 -1

output:

12070.567811865475

result:

ok found '12070.567811865', expected '12070.567811865', error '0.000000000'

Test #11:

score: -100
Time Limit Exceeded

input:

1604 10000
2604 -9655
7380 -6748
9963 859
9843 1765
-1452 9894
-2024 9793
-8862 4633
-2604 -9655
9301 3673
9871 -1601
-565 -9984
9640 -2659
9312 3645
-8291 -5591
7879 6158
1301 9915
509 9987
7757 -6311
-9301 -3673
7702 -6378
5415 8407
-9971 761
9023 -4311
-6785 7346
-9852 1714
-9788 -2048
9819 -1894...

output:


result: