QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#639990#1761. Knocked Inkoxford01#TL 291ms3872kbC++202.7kb2024-10-14 01:14:142024-10-14 01:14:14

Judging History

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

  • [2024-10-14 01:14:14]
  • 评测
  • 测评结果:TL
  • 用时:291ms
  • 内存:3872kb
  • [2024-10-14 01:14:14]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (auto i = a; i < (b); ++i)
#define repr(i, a, b) for (auto i = (a) - 1; i >= (b); --i)
#define pb push_back
#define eb emplace_back
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<pii>;

template<class T>
inline bool cmax(T &a, const T& b) {
    return a < b ? a = b, 1 : 0;
}

template<class T>
inline bool cmin(T &a, const T &b) {
    return b < a ? a = b, 1 : 0;
}

const int inf = 0x3f3f3f3f;
const ll linf = 1e18;
const double dinf = numeric_limits<double>::infinity();

template<class F>
double quad(double a, double b, F f, const int n = 50000) {
    double h = (b - a) / 2 / n, v = f(a) + f(b);
    rep(i, 1, n*2) 
        v += f(a + i * h) * (i & 1 ? 4 : 2);
    return v * h / 3;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int n;
    cin >> n;
    double a;
    cin >> a;

    vector<double> x(n), y(n), t(n);
    rep(i, 0, n) {
        cin >> x[i] >> y[i] >> t[i];
    }

    double lo = 0, hi = 2e6;

    rep(_, 0, 45) {
        double mid = (lo + hi) / 2;

        auto f = [&](double xx) {
            vector< pair<double, int> > ev;
            rep(i, 0, n) {
                if (t[i] >= mid) {
                    continue;
                }
                if (abs(x[i] - xx) > mid - t[i] - 1e-8) {
                    continue;
                }
                double d = sqrt((t[i]-mid)*(t[i]-mid) - (x[i]-xx)*(x[i]-xx));
                ev.eb(y[i] - d, 0);
                ev.eb(y[i] + d, 1);
            }
            sort(all(ev));
            int cnt = 0;
            double last, ans = 0.0;
            for (auto &[y, tt] : ev) {
                if (cnt > 0) {
                    ans += y - last;
                }
                if (tt == 0) {
                    ++cnt;
                } else {
                    --cnt;
                }
                last = y;
            }
            return ans;
        };

        
        // cerr << f(-10) << ' ' << f(10) << endl;

        double l = -1, r = 1;
        rep(i, 0, n) {
            if (mid > t[i]) {
                cmin(l, x[i] - (mid - t[i]));
                cmax(r, x[i] + (mid - t[i]));
            }
        }

        // cerr << mid << ' ' << f(0) << ' ' << qua f) << endl;

        if (quad(l - 10, r + 10, f) >= a) {
            hi = mid;
        } else {
            lo = mid;
        }
    }
    cout << fixed << setprecision(15) << lo << '\n';

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 291ms
memory: 3872kb

input:

2 1000000000
100 100 1000
99 101 999

output:

18840.172962995893613

result:

ok found '18840.1729630', expected '18840.1728537', error '0.0000000'

Test #2:

score: -100
Time Limit Exceeded

input:

40 1000000
0 0 0
0 1 0
0 2 0
0 3 0
0 4 0
0 5 0
0 6 0
0 7 0
0 8 0
0 9 0
0 10 0
1 10 0
2 10 0
3 10 0
4 10 0
5 10 0
6 10 0
7 10 0
8 10 0
9 10 0
10 10 0
10 9 0
10 8 0
10 7 0
10 6 0
10 5 0
10 4 0
10 3 0
10 2 0
10 1 0
10 0 0
9 0 0
8 0 0
7 0 0
6 0 0
5 0 0
4 0 0
3 0 0
2 0 0
1 0 0

output:


result: