QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#639990 | #1761. Knocked Ink | oxford01# | TL | 291ms | 3872kb | C++20 | 2.7kb | 2024-10-14 01:14:14 | 2024-10-14 01:14:14 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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