Submission details
Task:Keke's delivery service
Sender:aalto26jw_006
Submission time:2026-11-11 17:49:19 +0200
Language:C++ (C++23)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.00 sdetails
#15ACCEPTED0.00 sdetails
#16ACCEPTED0.00 sdetails
#17ACCEPTED0.00 sdetails
#18ACCEPTED0.00 sdetails
#19ACCEPTED0.00 sdetails
#20ACCEPTED0.00 sdetails
#21ACCEPTED0.00 sdetails
#22ACCEPTED0.00 sdetails
#23ACCEPTED0.00 sdetails
#24ACCEPTED0.00 sdetails
#25ACCEPTED0.00 sdetails
#26ACCEPTED0.00 sdetails
#27ACCEPTED0.00 sdetails
#28ACCEPTED0.00 sdetails
#29ACCEPTED0.00 sdetails
#30ACCEPTED0.00 sdetails
#31ACCEPTED0.00 sdetails
#32ACCEPTED0.00 sdetails
#33ACCEPTED0.01 sdetails
#34ACCEPTED0.01 sdetails
#35ACCEPTED0.01 sdetails
#36ACCEPTED0.01 sdetails
#37ACCEPTED0.01 sdetails
#38ACCEPTED0.01 sdetails
#39ACCEPTED0.01 sdetails
#40ACCEPTED0.01 sdetails
#41ACCEPTED0.01 sdetails
#42ACCEPTED0.01 sdetails
#43ACCEPTED0.01 sdetails
#44ACCEPTED0.01 sdetails
#45ACCEPTED0.01 sdetails
#46ACCEPTED0.01 sdetails
#47ACCEPTED0.01 sdetails
#48ACCEPTED0.04 sdetails
#49ACCEPTED0.04 sdetails
#50ACCEPTED0.04 sdetails
#51ACCEPTED0.04 sdetails
#52ACCEPTED0.04 sdetails
#53ACCEPTED0.13 sdetails
#54ACCEPTED0.13 sdetails
#55ACCEPTED0.14 sdetails
#56ACCEPTED0.14 sdetails
#57ACCEPTED0.13 sdetails
#58ACCEPTED0.14 sdetails
#59ACCEPTED0.13 sdetails
#60ACCEPTED0.14 sdetails
#61ACCEPTED0.14 sdetails
#62ACCEPTED0.14 sdetails

Code

// #ifdef ONLINE_JUDGE
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #endif
#include "bits/stdc++.h"
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fill(arr,val) memset(arr,val,sizeof(arr))
#define FOR(i, a, b) for(__typeof(b) i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for(__typeof(a) i = a, _b = b; i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define ii pair<int,int>
#define iii pair<int,pair<int,int>>
#define dq deque<int>
#define nend '\n'
using namespace std;

const ll inf = 1e18;
const int dx[] = {1,0,-1,0};
const int dy[] = {0,1,0,-1};
const int MOD = 1e9 + 7;
const ll hashi = 2e9 + 11;

void init_code() {
    fast;
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}
const int N=10, S=59049;
int n;
double px[2*N], py[2*N];  
double dp[S][2*N];
int pw3[N+1];

double dist(double x1, double y1, double x2, double y2) { return hypot(x1-x2, y1-y2); }

/// 0: not picked up 
/// 1: on the scooter 
/// 2: delivered
// dp[0..2][p] = shortest path from home that reaches this state, standing at point p
void solve() {
    cin >> n;
    FOR(i,0,n-1) cin >> px[2*i] >> py[2*i] >> px[2*i+1] >> py[2*i+1];
    pw3[0]=1;
    FOR(i,1,n) pw3[i]=pw3[i-1]*3;
    int full=pw3[n];
    FOR(s,0,full-1) FOR(p,0,2*n-1) dp[s][p]=1e30;
    FOR(i,0,n-1) dp[pw3[i]][2*i]=dist(0,0,px[2*i],py[2*i]);
    FOR(s,1,full-1) FOR(p,0,2*n-1) {
        double cur=dp[s][p];
        if (cur>=1e29) continue;
        FOR(i,0,n-1) {
            int st=s/pw3[i]%3;
            if (st==2) continue;
            int q=2*i+st;                  
            double nd=cur+dist(px[p],py[p],px[q],py[q]);
            double& t=dp[s+pw3[i]][q];
            if (nd<t) t=nd;
        }
    }
    int done=full-1;                        
    double ans=1e30;
    FOR(p,0,2*n-1) ans=min(ans, dp[done][p]+dist(px[p],py[p],0,0));
    cout << fixed << setprecision(10) << ans << nend;
}

int main() {
    init_code();

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
1
1 2 5 7 

correct output
17.24151748197526515596

user output
17.2415174820

Test 2

Verdict: ACCEPTED

input
1
-2 10 5 9 

correct output
27.56473698003804521928

user output
27.5647369800

Test 3

Verdict: ACCEPTED

input
2
-1 -7 -10 9 
1 9 -1 0 

correct output
46.64817201984418185146

user output
46.6481720198

Test 4

Verdict: ACCEPTED

input
2
1 -9 4 7 
-4 -8 0 1 

correct output
38.53321457061962859031

user output
38.5332145706

Test 5

Verdict: ACCEPTED

input
2
6 2 -6 8 
7 8 10 -7 

correct output
58.49347834429028263753

user output
58.4934783443

Test 6

Verdict: ACCEPTED

input
2
6 2 -6 8 
7 8 10 -7 

correct output
58.49347834429028263753

user output
58.4934783443

Test 7

Verdict: ACCEPTED

input
3
10 8 1 -7 
10 7 5 2 
4 2 -6 -8 

correct output
47.94841075476520489418

user output
47.9484107548

Test 8

Verdict: ACCEPTED

input
3
-6 -9 8 7 
-6 -3 9 10 
0 -9 2 -2 

correct output
53.42086935541394488933

user output
53.4208693554

Test 9

Verdict: ACCEPTED

input
3
8 9 -4 -6 
7 -9 -10 -3 
-8 10 2 -8 

correct output
75.43730966940650396746

user output
75.4373096694

Test 10

Verdict: ACCEPTED

input
3
8 4 2 -1 
-5 -8 -7 -7 
-2 -7 -8 -5 

correct output
41.03401888405835429979

user output
41.0340188841

Test 11

Verdict: ACCEPTED

input
3
-4 4 0 -4 
6 1 6 -8 
8 -8 -7 -6 

correct output
51.02746211319720185187

user output
51.0274621132

Test 12

Verdict: ACCEPTED

input
3
-1 -1 -4 4 
-6 -5 -5 -10 
7 4 -8 0 

correct output
49.16957315214831639866

user output
49.1695731521

Test 13

Verdict: ACCEPTED

input
3
5 -9 2 5 
9 7 -7 8 
6 -9 -3 9 

correct output
56.01093630215238362152

user output
56.0109363022

Test 14

Verdict: ACCEPTED

input
4
-9 -6 6 -4 
-1 10 5 -1 
10 -4 1 -5 
0 -9 -9 -2 

correct output
69.46799309053363308958

user output
69.4679930905

Test 15

Verdict: ACCEPTED

input
4
8 -10 10 -5 
8 -3 1 7 
-6 -2 -10 2 
-1 6 -2 -2 

correct output
62.32599841627421704063

user output
62.3259984163

Test 16

Verdict: ACCEPTED

input
4
-10 -3 0 0 
0 -10 -8 -4 
-8 -10 -6 8 
-2 -8 -5 -8 

correct output
49.37474628842959419733

user output
49.3747462884

Test 17

Verdict: ACCEPTED

input
4
9 -10 3 -3 
5 -10 -8 6 
-9 -3 6 8 
-4 5 1 4 

correct output
70.54491148050797239000

user output
70.5449114805

Test 18

Verdict: ACCEPTED

input
4
3 2 0 9 
1 3 8 5 
4 -6 5 -8 
5 7 -6 10 

correct output
55.77371783018015604511

user output
55.7737178302

Test 19

Verdict: ACCEPTED

input
4
4 5 0 7 
7 5 -10 4 
6 -6 1 10 
-4 2 -10 0 

correct output
58.25155150420911822143

user output
58.2515515042

Test 20

Verdict: ACCEPTED

input
4
-7 3 -4 -6 
-9 3 -1 -5 
7 1 9 2 
5 5 6 8 

correct output
51.95472904146592808827

user output
51.9547290415

Test 21

Verdict: ACCEPTED

input
4
8 3 -7 6 
0 6 9 -8 
-2 8 -9 -9 
9 -6 3 -2 

correct output
71.27875557664922673284

user output
71.2787555766

Test 22

Verdict: ACCEPTED

input
4
6 -7 1 10 
-8 -6 3 -9 
-9 -7 -4 -9 
-2 5 1 -7 

correct output
64.30357123791869498886

user output
64.3035712379

Test 23

Verdict: ACCEPTED

input
5
3 9 -3 -6 
3 -2 -7 3 
10 4 -3 2 
10 9 -6 4 
...

correct output
65.29921928785613079865

user output
65.2992192879

Test 24

Verdict: ACCEPTED

input
5
-4 -10 10 -4 
6 2 10 3 
-6 -3 -8 -6 
9 9 -9 9 
...

correct output
82.23748773331917538004

user output
82.2374877333

Test 25

Verdict: ACCEPTED

input
5
8 -9 -3 -2 
1 -4 10 5 
5 5 7 -3 
-8 -1 9 -5 
...

correct output
67.56153807887115932823

user output
67.5615380789

Test 26

Verdict: ACCEPTED

input
5
-5 4 -1 4 
-2 9 -5 -8 
8 5 -7 2 
-10 7 10 8 
...

correct output
86.95689997133690237602

user output
86.9568999713

Test 27

Verdict: ACCEPTED

input
5
-10 -6 6 -2 
-9 -2 3 -1 
-10 -8 9 5 
-2 -3 -5 -2 
...

correct output
60.24622192778474186192

user output
60.2462219278

Test 28

Verdict: ACCEPTED

input
5
-1 -1 -4 4 
-6 -5 -5 -10 
7 4 -8 0 
3 2 -5 -5 
...

correct output
56.09845589945781874422

user output
56.0984558995

Test 29

Verdict: ACCEPTED

input
5
5 -9 2 5 
9 7 -7 8 
6 -9 -3 9 
-7 0 -5 -2 
...

correct output
66.46035926536274213855

user output
66.4603592654

Test 30

Verdict: ACCEPTED

input
5
9 -8 -1 1 
-6 5 2 -4 
3 8 4 -9 
-8 3 5 3 
...

correct output
68.92236432287188030443

user output
68.9223643229

Test 31

Verdict: ACCEPTED

input
5
-2 8 8 9 
9 8 4 -2 
3 9 2 1 
-6 -7 -2 -8 
...

correct output
68.57347683433427024124

user output
68.5734768343

Test 32

Verdict: ACCEPTED

input
5
1 -10 6 7 
7 -3 -8 7 
2 2 1 -2 
-1 -6 -1 4 
...

correct output
67.26306049003909036388

user output
67.2630604900

Test 33

Verdict: ACCEPTED

input
6
633196515 485923574 -954265220...

correct output
7364359200.7228123750537633895...

user output
7364359200.7228116989

Test 34

Verdict: ACCEPTED

input
6
-54250287 -57195506 925370083 ...

correct output
6070544873.2142193284817039966...

user output
6070544873.2142190933

Test 35

Verdict: ACCEPTED

input
6
717786754 -23244255 -670216484...

correct output
6236901804.9330618907697498798...

user output
6236901804.9330625534

Test 36

Verdict: ACCEPTED

input
6
-747595481 -560868740 20781968...

correct output
6206348638.7408930636011064052...

user output
6206348638.7408933640

Test 37

Verdict: ACCEPTED

input
6
369551931 -830851741 -63146575...

correct output
7466232851.6345729152671992778...

user output
7466232851.6345710754

Test 38

Verdict: ACCEPTED

input
7
-503438465 -401188031 -2915208...

correct output
7182008964.6697172718122601509...

user output
7182008964.6697168350

Test 39

Verdict: ACCEPTED

input
7
-774852389 498112692 -73382627...

correct output
7322574754.7929240637458860874...

user output
7322574754.7929239273

Test 40

Verdict: ACCEPTED

input
7
-745557241 -362230062 11872950...

correct output
7345290128.8702740180306136608...

user output
7345290128.8702754974

Test 41

Verdict: ACCEPTED

input
7
-280510503 487323735 82609299 ...

correct output
8284167601.0197063554078340530...

user output
8284167601.0197076797

Test 42

Verdict: ACCEPTED

input
7
-194568921 -912512861 44703011...

correct output
9098246106.3207166725769639015...

user output
9098246106.3207187653

Test 43

Verdict: ACCEPTED

input
8
383287698 969195218 -182348842...

correct output
7016551085.8444829522632062435...

user output
7016551085.8444814682

Test 44

Verdict: ACCEPTED

input
8
-385704087 -937741013 -3077950...

correct output
8127710933.8054637983441352844...

user output
8127710933.8054647446

Test 45

Verdict: ACCEPTED

input
8
844450667 -871888619 -19960889...

correct output
8213584640.6935460437089204788...

user output
8213584640.6935462952

Test 46

Verdict: ACCEPTED

input
8
-466328566 481082051 -33685140...

correct output
9423990911.6089521860703825950...

user output
9423990911.6089534760

Test 47

Verdict: ACCEPTED

input
8
-917189424 -579600323 67525298...

correct output
8227519630.3055775831453502178...

user output
8227519630.3055772781

Test 48

Verdict: ACCEPTED

input
9
-31221656 -526597392 -52535813...

correct output
8856995290.3726284708827733993...

user output
8856995290.3726291656

Test 49

Verdict: ACCEPTED

input
9
-23884334 -938550432 -56172498...

correct output
7357984723.6206405288539826870...

user output
7357984723.6206407547

Test 50

Verdict: ACCEPTED

input
9
-114003248 747828772 -69571861...

correct output
7938964098.6173283923417329788...

user output
7938964098.6173295975

Test 51

Verdict: ACCEPTED

input
9
166708726 -263032442 565409766...

correct output
7766653103.2631514174863696098...

user output
7766653103.2631511688

Test 52

Verdict: ACCEPTED

input
9
-325935302 409170424 652212820...

correct output
8170515916.9658243129961192607...

user output
8170515916.9658241272

Test 53

Verdict: ACCEPTED

input
10
178568022 273124119 535857466 ...

correct output
8231356926.8400429780595004558...

user output
8231356926.8400421143

Test 54

Verdict: ACCEPTED

input
10
-104452078 546885062 -99975436...

correct output
9390756029.7148792939260601997...

user output
9390756029.7148780823

Test 55

Verdict: ACCEPTED

input
10
-63708076 -602539257 -94432385...

correct output
8497255968.9021178991533815860...

user output
8497255968.9021167755

Test 56

Verdict: ACCEPTED

input
10
182829493 -848119476 520735868...

correct output
9795917686.1810622680932283401...

user output
9795917686.1810626984

Test 57

Verdict: ACCEPTED

input
10
934069847 175172315 -629139614...

correct output
10107572824.729460356757044792...

user output
10107572824.7294597626

Test 58

Verdict: ACCEPTED

input
10
-523273295 -881501593 86988338...

correct output
9378626642.9278714880347251892...

user output
9378626642.9278717041

Test 59

Verdict: ACCEPTED

input
10
917402565 -287078799 -55030325...

correct output
9067761971.7593543389812111854...

user output
9067761971.7593536377

Test 60

Verdict: ACCEPTED

input
10
-836129193 -511793054 67486286...

correct output
9294216739.0473321685567498207...

user output
9294216739.0473327637

Test 61

Verdict: ACCEPTED

input
10
875675361 -976131926 -48580743...

correct output
10188158256.107221888378262519...

user output
10188158256.1072196960

Test 62

Verdict: ACCEPTED

input
10
-977721665 -217325906 77767487...

correct output
9173124717.6331664901226758956...

user output
9173124717.6331672668