Rezultati

Up. imeNalogaJezikRezultatČas oddaje
final-solution-2019 Premikanje pohištva C 0/100Napačen odgovor (WA) 24. apr '19 @ 20:11

Test Točke Porabljen spomin Porabljen čas Status
#1 [več] 2/2 3,496 MiB 0,000 s OK
#2 [več] 0/2 3,473 MiB 0,000 s Napačen odgovor
#3 [več] 0/2 3,473 MiB 0,000 s Napačen odgovor
#4 [več] 0/2 3,500 MiB 0,005 s Napačen odgovor
#5 [več] 0/2 3,473 MiB 0,000 s Napačen odgovor
#6 [več] 0/2 3,539 MiB 0,005 s Napačen odgovor
#7 [več] 0/2 3,516 MiB 0,000 s Napačen odgovor
#8 [več] 0/2 3,516 MiB 0,005 s Napačen odgovor
#9 [več] 0/2 3,516 MiB 0,000 s Napačen odgovor
#10 [več] 0/2 3,488 MiB 0,000 s Napačen odgovor
#11 [več] 0/2 3,492 MiB 0,000 s Napačen odgovor
#12 [več] 0/2 3,723 MiB 0,004 s Napačen odgovor
#13 [več] 0/2 3,695 MiB 0,010 s Napačen odgovor
#14 [več] 0/2 3,695 MiB 0,010 s Napačen odgovor
#15 [več] 0/2 3,727 MiB 0,016 s Napačen odgovor
#16 [več] 0/2 3,695 MiB 0,004 s Napačen odgovor
#17 [več] 0/2 3,699 MiB 0,016 s Napačen odgovor
#18 [več] 0/2 3,695 MiB 0,010 s Napačen odgovor
#19 [več] 0/2 3,727 MiB 0,010 s Napačen odgovor
#20 [več] 0/2 3,695 MiB 0,010 s Napačen odgovor
#21 [več] 0/2 3,695 MiB 0,004 s Napačen odgovor
#22 [več] 0/2 3,723 MiB 0,010 s Napačen odgovor
#23 [več] 0/2 3,723 MiB 0,004 s Napačen odgovor
#24 [več] 0/2 3,727 MiB 0,004 s Napačen odgovor
#25 [več] 0/2 3,727 MiB 0,004 s Napačen odgovor
#26 [več] 0/2 3,727 MiB 0,016 s Napačen odgovor
#27 [več] 0/2 6,059 MiB 0,081 s Napačen odgovor
#28 [več] 0/2 6,051 MiB 0,063 s Napačen odgovor
#29 [več] 0/2 6,059 MiB 0,069 s Napačen odgovor
#30 [več] 0/2 6,059 MiB 0,069 s Napačen odgovor
#31 [več] 0/2 6,055 MiB 0,081 s Napačen odgovor
#32 [več] 0/2 6,055 MiB 0,081 s Napačen odgovor
#33 [več] 2/2 6,059 MiB 0,081 s OK
#34 [več] 0/2 6,035 MiB 0,105 s Napačen odgovor
#35 [več] 0/2 6,035 MiB 0,044 s Napačen odgovor
#36 [več] 0/2 6,031 MiB 0,063 s Napačen odgovor
#37 [več] 0/2 6,035 MiB 0,069 s Napačen odgovor
#38 [več] 0/2 6,063 MiB 0,081 s Napačen odgovor
#39 [več] 0/2 6,031 MiB 0,087 s Napačen odgovor
#40 [več] 0/2 6,063 MiB 0,087 s Napačen odgovor
#41 [več] 0/2 6,035 MiB 0,081 s Napačen odgovor
#42 [več] 0/2 6,063 MiB 0,081 s Napačen odgovor
#43 [več] 0/2 6,035 MiB 0,075 s Napačen odgovor
#44 [več] 0/2 6,063 MiB 0,075 s Napačen odgovor
#45 [več] 0/3 6,063 MiB 0,087 s Napačen odgovor
#46 [več] 3/3 3,473 MiB 0,005 s OK
#47 [več] 0/3 3,473 MiB 0,000 s Napačen odgovor
#48 [več] 0/3 6,031 MiB 0,065 s Napačen odgovor

Ocenjevani program (premikanje.c):
#include <stdio.h>

static int N = 0;
static long long X[100001];
static long long Y[100001];
static long long XS[100001];
static long long YS[100001];
static long long X2S[100001];
static long long Y2S[100001];

static double avg_r(const long long *as, int s, int e) {
    if (s == e) return 0;
    return (as[e]-as[s])/(double)(e-s);
}

static double sq_dist(const long long *as, const long long *a2s, int s, int e, double avg) {
    if (s == e) return 0;
    return (a2s[e]-a2s[s]) - 2*avg*(as[e]-as[s]) + avg*avg*(e-s);
}

static double solve(const long long *as, const long long *a2s) {
    double r = 0;
    int s = 0, e = 1;
    while (s < N) {
        double md = 0, md1 = 0;
        int h = 0;
        for (; e <= N; e++) {
            double a1 = avg_r(as, s, e);
            double a2 = avg_r(as, e, N);
            double d1 = sq_dist(as, a2s, s, e, a1);
            double d2 = sq_dist(as, a2s, e, N, a2);
            if (a1 <= a2) {
                if (!h || d1+d2 <= md) {
                    md = d1+d2;
                    md1 = d1;
                    h = 1;
                }
                else break;
            }
        }
        r += md1;
        s = e;
        e = s + 1;
    }
    return r;
}

int main() {
    int i = 0;
    scanf("%d", &N);
    for (; i < N; i++) {
        scanf("%lld %lld", X + i, Y + i);
        XS[i+1] = X[i] + XS[i];
        YS[i+1] = Y[i] + YS[i];
        X2S[i+1] = X[i]*X[i] + X2S[i];
        Y2S[i+1] = Y[i]*Y[i] + Y2S[i];
    }
    double r = solve(XS, X2S) + solve(YS, Y2S);
    printf("%.12f\n", r);
    return 0;
}