Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Слава Україні, Героям слава
- #include <bits/stdc++.h>
- using namespace std;
- using ld = long double;
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout << setprecision(15) << fixed;
- ld x, y;
- cin >> x >> y;
- ld xi, yi;
- cin >> xi >> yi;
- ld vr, vs;
- cin >> vr >> vs;
- int n, s;
- cin >> n >> s;
- vector<pair<int, int>> v(n);
- for(int i = 0; i < n; i++) {
- cin >> v[i].first >> v[i].second;
- }
- vector<vector<ld>> f_tsp(n, vector<ld>(1 << n, numeric_limits<ld>::infinity())), dist(n, vector<ld>(n)), dp(n, vector<ld>(1 << n, numeric_limits<ld>::infinity()));
- vector<ld> to_icecream(1 << n, numeric_limits<ld>::infinity()), b2b(1 << n, numeric_limits<ld>::infinity());
- function<ld(ld, ld, ld, ld)> calc = [&](ld a, ld b, ld c, ld d) {
- ld l = -1e6, r = 1e6;
- for(int _ = 0; _ < 100; _++) {
- ld m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
- ld t1 = sqrtl((a - m1) * (a - m1) + b * b) / vr + sqrtl((c - m1) * (c - m1) + d * d) / vs;
- ld t2 = sqrtl((a - m2) * (a - m2) + b * b) / vr + sqrtl((c - m2) * (c - m2) + d * d) / vs;
- if(t1 > t2) {
- l = m1;
- } else {
- r = m2;
- }
- }
- return sqrtl((a - l) * (a - l) + b * b) / vr + sqrtl((c - l) * (c - l) + d * d) / vs;
- };
- for(int i = 0; i < n; i++) {
- f_tsp[i][1 << i] = calc(x, y, v[i].first, v[i].second);
- dp[i][1 << i] = calc(xi, yi, v[i].first, v[i].second);
- }
- function<ld(int, int)> calc2 = [&](int i, int j) {
- ld l = 0, r = abs(v[i].first - v[j].first);
- for(int _ = 0; _ < 100; _++) {
- ld m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
- ld t1 = hypotl(abs(v[i].first - v[j].first) - m1, v[i].second + v[j].second) / vs + m1 / vr;
- ld t2 = hypotl(abs(v[i].first - v[j].first) - m2, v[i].second + v[j].second) / vs + m2 / vr;
- if(t1 > t2) {
- l = m1;
- } else {
- r = m2;
- }
- }
- return hypotl(abs(v[i].first - v[j].first) - l, v[i].second + v[j].second) / vs + l / vr;
- };
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < n; j++) {
- if(i == j) {
- dist[i][j] = 0;
- continue;
- }
- dist[i][j] = hypotl(v[i].first - v[j].first, v[i].second - v[j].second) / vs;
- dist[i][j] = min(dist[i][j], calc2(i, j));
- }
- }
- for(int msk = 1; msk < (1 << n); msk++) {
- for(int j = 0; j < n; j++) {
- for(int k = 0; k < n; k++) {
- if((msk >> j) & 1 and !((msk >> k) & 1)) {
- f_tsp[k][msk ^ (1 << k)] = min(f_tsp[k][msk ^ (1 << k)], f_tsp[j][msk] + dist[j][k]);
- }
- }
- if((msk >> j) & 1) {
- to_icecream[msk] = min(to_icecream[msk], f_tsp[j][msk] + calc(xi, yi, v[j].first, v[j].second));
- }
- }
- }
- for(int msk = 1; msk < (1 << n); msk++) {
- for(int j = 0; j < n; j++) {
- for(int k = 0; k < n; k++) {
- if((msk >> j) & 1 and !((msk >> k) & 1)) {
- dp[k][msk ^ (1 << k)] = min(dp[k][msk ^ (1 << k)], dp[j][msk] + dist[j][k]);
- }
- }
- if((msk >> j) & 1) {
- b2b[msk] = min(b2b[msk], dp[j][msk] + calc(xi, yi, v[j].first, v[j].second));
- }
- }
- }
- vector<ld> dp2(1 << n, numeric_limits<ld>::infinity());
- dp2[0] = 0;
- for(int msk = 1; msk < (1 << n); msk++) {
- if(__builtin_popcount(msk) <= s) {
- dp2[msk] = to_icecream[msk];
- }
- for(int sm = msk; sm; sm = (sm - 1) & msk) {
- int falta = msk ^ sm;
- if(__builtin_popcount(falta) <= s) {
- dp2[msk] = min(dp2[msk], dp2[sm] + b2b[falta]);
- }
- }
- }
- cout << dp2.back() << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement