QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#102680#3186. Cent SavingsPetroTarnavskyi#RE 0ms0kbC++172.1kb2023-05-03 15:58:542023-05-03 15:58:58

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-03 15:58:58]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-05-03 15:58:54]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

5 1
13 21 55 60 42

output:


result: