QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#102680 | #3186. Cent Savings | PetroTarnavskyi# | RE | 0ms | 0kb | C++17 | 2.1kb | 2023-05-03 15:58:54 | 2023-05-03 15:58:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef double db;
#define y1 zhepa
const int N = 1 << 10;
db dist(db x1, db y1, db x2, db y2) {
return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
db vWalk, vBike, x1, y1, x2, y2, xg, yg, xd, yd;
db xs[N], ys[N], dg[N], dd[N];
db f(db xb, db yb, db xe, db ye, db xs1, db ys1, db xs2, db ys2) {
db l = 0, r = 1;
db ans;
FOR(i, 0, 1000) {
db m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
db xm1 = (1 - m1) * xs1 + m1 * xs2, ym1 = (1 - m1) * ys1 + m1 * ys2,
xm2 = (1 - m2) * xs1 + m2 * xs2, ym2 = (1 - m2) * ys1 + m2 * ys2;
db f1 = dist(xb, xm1, yb, ym1) / vWalk + dist(xm1, xe, ym1, ye) / vBike,
f2 = dist(xb, xm2, yb, ym2) / vWalk + dist(xm2, xe, ym2, ye) / vBike;
if (f1 < f2) {
r = m2;
}
else {
l = m1;
}
ans = f1;
}
return ans;
}
db f(db xb, db yb, db xe, db ye) {
db ans = 1e47;
ans = min(ans, f(xb, yb, xe, ye, x1, y1, x2, y1));
ans = min(ans, f(xb, yb, xe, ye, x2, y1, x2, y2));
ans = min(ans, f(xb, yb, xe, ye, x2, y2, x1, y2));
ans = min(ans, f(xb, yb, xe, ye, x1, y2, x1, y1));
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(10);
cin >> vWalk >> vBike >> x1 >> y1 >> x2 >> y2 >> xg >> yg >> xd >> yd;
int n;
cin >> n;
FOR(i, 0, n) {
cin >> xs[i] >> ys[i];
dg[i] = dist(xs[i], ys[i], xg, yg);
dd[i] = dist(xs[i], ys[i], xd, yd);
}
db ans = dist(xg, yg, xd, yg) / vWalk;
FOR(i, 0, n) {
FOR(j, 0, n) {
ans = min(ans, (dg[i] + dd[j]) / vWalk + dist(xs[i], ys[i], xs[j], ys[j]) / vBike);
}
ans = min(ans, dg[i] / vWalk + f(xd, yd, xs[i], ys[i]));
ans = min(ans, dd[i] / vWalk + f(xg, yg, xs[i], ys[i]));
}
cout << ans << "\n";
return 0;
}
详细
Test #1:
score: 0
Runtime Error
input:
5 1 13 21 55 60 42