QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#367530 | #8513. Insects, Mathematics, Accuracy, and Efficiency | hos_lyric | TL | 1ms | 4136kb | C++14 | 6.9kb | 2024-03-26 05:14:08 | 2024-03-26 05:14:08 |
Judging History
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...