QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#291122#3246. 喵喵花園MoRanSkyAC ✓615ms167508kbC++237.0kb2023-12-26 04:58:532023-12-26 04:58:54

Judging History

This is the latest submission verdict.

  • [2023-12-26 04:58:54]
  • Judged
  • Verdict: AC
  • Time: 615ms
  • Memory: 167508kb
  • [2023-12-26 04:58:53]
  • Submitted

answer

// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define y1 dmytxdy

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

template <typename T> bool chkMax(T &x, T y) {
    return (y > x) ? x = y, 1 : 0;
}
template <typename T> bool chkMin(T &x, T y) {
    return (y < x) ? x = y, 1 : 0;
}

template <typename T> void inline read(T &x) {
    int f = 1;
    x = 0;
    char s = getchar();

    while (s < '0' || s > '9') {
        if (s == '-')
            f = -1;

        s = getchar();
    }

    while (s <= '9' && s >= '0')
        x = x * 10 + (s ^ 48), s = getchar();

    x *= f;
}


typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;

template <typename T> bool chkmin(T &x, T y) {
    return x > y ? x = y, 1 : 0;
}
template <typename T> bool chkmax(T &x, T y) {
    return x < y ? x = y, 1 : 0;
}

int readint() {
    int x = 0, f = 1;
    char ch = getchar();

    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;

        ch = getchar();
    }

    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }

    return x * f;
}

const int N = 1005;

const long double eps = 1e-6;
typedef pair<long double, long double> PDD;

int inline cmp(long double x, long double y) {
    if (fabs(x - y) < eps)
        return 0;

    return x < y ? -1 : 1;
}

long double inline cross(PDD a, PDD b) {
    return a.fi * b.se - a.se * b.fi;
}
PDD operator - (const PDD &a, const PDD &b) {
    return make_pair(a.fi - b.fi, a.se - b.se);
}
PDD operator + (const PDD &a, const PDD &b) {
    return make_pair(a.fi + b.fi, a.se + b.se);
}
PDD operator / (const PDD &a, long double b) {
    return make_pair(a.fi / b, a.se / b);
}
PDD operator * (const PDD &a, long double b) {
    return make_pair(a.fi * b, a.se * b);
}
long double inline area(PDD a, PDD b, PDD c) {
    return cross(b - a, c - a);
}
long double inline dot(PDD a, PDD b) {
    return a.fi * b.fi + a.se * b.se;
}
long double inline len(PDD a) {
    return sqrt(dot(a, a));
}
long double inline project(PDD a, PDD b, PDD c) {
    return dot(b - a, c - a) / len(b - a);
}
long double inline dist(PDD a, PDD b) {
    return sqrt((a.fi - b.fi) * (a.fi - b.fi) + (a.se - b.se) * (a.se - b.se));
}
// 顺时针转 x
PDD inline rotate(PDD a, long double x) {
    return make_pair(cos(x) * a.fi + sin(x) * a.se, -sin(x) * a.fi + cos(x) * a.se);
}
PDD inline norm(PDD a) {
    return a / len(a);
}
long double angle(PDD a, PDD b) {
    return acos(dot(a, b) / len(a) / len(b));
}

int n, k;

PDD a[N];

long double L = 0;

PDD x1[N], y1[N];

long double lim[N];

struct Line {
    int op;
    long double L, kx, bx, ky, by;
    bool operator < (const Line &b) const {
        return L < b.L;
    }
};

struct AC {
    int o;
    long double x, A, B, C;
    bool operator < (const AC &b) const {
        return x < b.x;
    }
} ct[N];

vector<AC> e;

vector<Line> X;

long double inline mod(long double k) {
    if (k >= L)
        k -= L;

    return k;
}

void bd(long double o, int op) {
    for (int i = 1; i <= n; i++) {
        if (lim[i] + o <= L && lim[i + 1] + o > L) {
            X.pb((Line) {
                op, lim[i] + o, x1[i].fi, x1[i].se - x1[i].fi *o, y1[i].fi, y1[i].se - y1[i].fi *o
            });
            X.pb((Line) {
                op, 0, x1[i].fi, x1[i].se - x1[i].fi * (o - L), y1[i].fi, y1[i].se - y1[i].fi * (o - L)
            });
            //  puts("tototot\n");
        } else if (lim[i] + o <= L) {
            X.pb((Line) {
                op, lim[i] + o, x1[i].fi, x1[i].se - x1[i].fi *o, y1[i].fi, y1[i].se - y1[i].fi *o
            });
        } else {
            X.pb((Line) {
                op, lim[i] + o - L, x1[i].fi, x1[i].se - x1[i].fi * (o - L), y1[i].fi, y1[i].se - y1[i].fi * (o - L)
            });
        }
    }
}

Line cur[2];



long double A, B, C, ans = 1e18, le, re;

void inline calc(long double x) {
    if (cmp(x, le) == -1 || cmp(x, re) == 1)
        return;

    long double val = x * x * A + B * x + C;
    //if (val < 0) return;
    chkMin(ans, val);
}

void inline upd() {
    calc(le);
    calc(re);
    calc(-B / A / 2);
}

int main() {
    //freopen("1.in", "r", stdin);
    n = readint();
    k = readint();

    for (int i = 1; i <= n; i++)
        a[i].fi = readint(), a[i].se = readint();

    a[n + 1] = a[1];

    for (int i = 1; i <= n; i++)
        L += dist(a[i], a[i + 1]);

    long double now = 0;
    long double D = L / k;

    for (int i = 1; i <= n; i++) {
        long double len = dist(a[i], a[i + 1]);
        x1[i] = mp((a[i + 1].fi - a[i].fi) / len, a[i].fi);
        y1[i] = mp((a[i + 1].se - a[i].se) / len, a[i].se);
        x1[i].se -= x1[i].fi * now;
        y1[i].se -= y1[i].fi * now;
        lim[i] = now;
        //  cout << x1[i].fi << " " << x1[i].se << "---" << y1[i].fi << " " << y1[i].se << " ji\n";
        now += len;
    }

    lim[n + 1] = now;

    //cout << D <<" ??aaa\n";
    for (int i = 0; i < k; i++) {
        X.clear();
        long double B = D * i, A = D * (i + 1);

        if (i == k - 1)
            A = 0;

        bd(A, 0);
        bd(B, 1);
        //cout << " now it show time for " << A << " " << B << "??\n";
        sort(X.begin(), X.end());

        for (int j = 0; j < X.size(); j++) {
            Line o = X[j];
            cur[o.op] = o;

            if (j + 1 < X.size() && !cmp(X[j].L, X[j + 1].L))
                continue;

            //  cout << o.L << "->>\n" << cur[0].kx << " " << cur[0].bx << " " << cur[0].ky << " " << cur[0].by << endl;
            //  cout << o.L << "->>\n" << cur[1].kx << " " << cur[1].bx << " " << cur[1].ky << " " << cur[1].by << endl;
            //  cout << 0 << " " << o.L << "->>\n" << cur[0].kx * o.L + cur[0].bx << " " << cur[0].ky * o.L + cur[0].by << endl;
            //  cout << 1 << " "<< o.L << "->>\n" << cur[1].kx * o.L + cur[1].bx << " " << cur[1].ky * o.L + cur[1].by << endl;
            e.pb((AC) {
                i, o.L, (cur[0].kx * cur[1].ky - cur[1].kx * cur[0].ky),
                cur[0].kx *cur[1].by + cur[0].bx *cur[1].ky - (cur[1].kx * cur[0].by + cur[1].bx * cur[0].ky),
                cur[0].bx *cur[1].by - cur[1].bx *cur[0].by
            });
        }
    }

    sort(e.begin(), e.end());

    for (int i = 0; i < e.size(); i++) {
        int u = e[i].o;
        A -= ct[u].A, B -= ct[u].B, C -= ct[u].C;
        ct[u] = e[i];
        A += ct[u].A, B += ct[u].B, C += ct[u].C;

        if (i + 1 < e.size() && !cmp(e[i].x, e[i + 1].x))
            continue;

        le = e[i].x, re = L;

        if (i + 1 < e.size())
            re = e[i + 1].x;

        //      cout << i << " " << le << " " << re << "zjsw??\n";
        upd();
    }

    printf("%.10Lf\n", ans / 2);
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 485ms
memory: 167216kb

input:

1000 800
-99983 -1896
-99971 -2447
-99942 -3427
-99935 -3623
-99923 -3942
-99902 -4444
-99864 -5228
-99835 -5757
-99827 -5896
-99815 -6095
-99811 -6160
-99801 -6317
-99795 -6411
-99732 -7330
-99699 -7765
-99687 -7919
-99642 -8464
-99610 -8830
-99587 -9087
-99538 -9611
-99526 -9734
-99495 -10047
-994...

output:

31414852000.4136614799

result:

ok found '31414852000.413661957', expected '31414852000.414176941', error '0.000000000'

Test #2:

score: 0
Accepted
time: 521ms
memory: 167508kb

input:

1000 900
-99999 -632
-99993 -1258
-99990 -1472
-99986 -1724
-99981 -1997
-99957 -2961
-99955 -3024
-99949 -3211
-99932 -3712
-99908 -4311
-99895 -4599
-99861 -5290
-99835 -5757
-99806 -6239
-99791 -6476
-99750 -7078
-99707 -7660
-99608 -8855
-99572 -9249
-99539 -9599
-99505 -9947
-99493 -10066
-9938...

output:

31415015242.8877042774

result:

ok found '31415015242.887702942', expected '31415015242.887584686', error '0.000000000'

Test #3:

score: 0
Accepted
time: 615ms
memory: 167316kb

input:

1000 1000
-99997 -883
-99992 -1336
-99990 -1474
-99986 -1723
-99713 -7581
-99700 -7752
-99660 -8251
-99604 -8901
-99545 -9536
-99494 -10057
-99436 -10612
-99351 -11383
-99240 -12313
-99192 -12692
-99100 -13393
-99072 -13599
-99015 -14008
-98973 -14302
-98825 -15291
-98783 -15560
-98725 -15924
-98687...

output:

31414938256.4498835802

result:

ok found '31414938256.449882507', expected '31414938256.450866699', error '0.000000000'

Test #4:

score: 0
Accepted
time: 252ms
memory: 85392kb

input:

900 500
-100000 -378
-99990 -1474
-99987 -1657
-99971 -2447
-99968 -2567
-99909 -4273
-99870 -5111
-99857 -5362
-99843 -5619
-99673 -8089
-99644 -8442
-99605 -8890
-99545 -9536
-99412 -10838
-99377 -11153
-99148 -13034
-99130 -13170
-99079 -13548
-99002 -14098
-98810 -15388
-98338 -18160
-98252 -186...

output:

31414085412.4212222416

result:

ok found '31414085412.421222687', expected '31414085412.421134949', error '0.000000000'

Test #5:

score: 0
Accepted
time: 219ms
memory: 85476kb

input:

900 400
-100000 -337
-99999 -575
-99997 -875
-99996 -991
-99995 -1080
-99991 -1400
-99990 -1469
-99967 -2600
-99965 -2675
-99944 -3367
-99896 -4576
-99873 -5052
-99802 -6305
-99690 -7879
-99654 -8319
-99576 -9210
-99507 -9927
-99430 -10671
-99404 -10909
-99317 -11676
-99105 -13357
-99076 -13570
-990...

output:

31413800407.1723493319

result:

ok found '31413800407.172348022', expected '31413800407.172279358', error '0.000000000'

Test #6:

score: 0
Accepted
time: 411ms
memory: 167348kb

input:

900 800
-99998 -758
-99995 -1096
-99988 -1611
-99981 -1998
-99971 -2447
-99963 -2752
-99862 -5261
-99728 -7384
-99524 -9755
-99511 -9885
-99490 -10094
-99452 -10462
-99397 -10974
-99382 -11109
-99255 -12191
-99074 -13582
-98847 -15148
-98690 -16139
-98542 -17019
-98508 -17214
-98461 -17482
-98377 -1...

output:

31414646664.5007420778

result:

ok found '31414646664.500743866', expected '31414646664.500938416', error '0.000000000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 7360kb

input:

1000 10
-99998 -754
-99991 -1400
-99986 -1728
-99981 -2000
-99973 -2361
-99969 -2528
-99959 -2893
-99928 -3808
-99915 -4142
-99870 -5115
-99846 -5565
-99834 -5775
-99723 -7451
-99690 -7879
-99643 -8452
-99625 -8664
-99606 -8879
-99509 -9908
-99289 -11910
-99194 -12679
-98942 -14515
-98847 -15147
-98...

output:

29387236138.6524098460

result:

ok found '29387236138.652408600', expected '29387236138.652404785', error '0.000000000'

Test #8:

score: 0
Accepted
time: 4ms
memory: 10516kb

input:

1000 20
-99998 -766
-99988 -1579
-99945 -3345
-99915 -4134
-99854 -5418
-99760 -6937
-99709 -7634
-99623 -8684
-99563 -9349
-99403 -10918
-99368 -11232
-99345 -11435
-99327 -11590
-99233 -12370
-99086 -13496
-99054 -13729
-99041 -13822
-98939 -14535
-98910 -14731
-98851 -15122
-98846 -15155
-98791 -...

output:

30900099346.9495120049

result:

ok found '30900099346.949512482', expected '30900099346.949504852', error '0.000000000'

Test #9:

score: 0
Accepted
time: 17ms
memory: 9436kb

input:

1000 30
-99991 -1389
-99970 -2490
-99957 -2963
-99937 -3574
-99933 -3685
-99929 -3789
-99871 -5095
-99789 -6508
-99776 -6705
-99760 -6938
-99731 -7343
-99723 -7452
-99642 -8464
-99599 -8956
-99451 -10474
-99427 -10699
-99338 -11494
-99294 -11869
-99270 -12067
-99201 -12623
-99193 -12686
-99169 -1287...

output:

31185342172.6591391321

result:

ok found '31185342172.659137726', expected '31185342172.659126282', error '0.000000000'

Test #10:

score: 0
Accepted
time: 24ms
memory: 14956kb

input:

1000 40
-99999 -616
-99993 -1240
-99989 -1527
-99975 -2271
-99957 -2954
-99925 -3887
-99904 -4397
-99880 -4918
-99838 -5707
-99790 -6493
-99763 -6893
-99743 -7178
-99729 -7370
-99713 -7584
-99668 -8152
-99648 -8393
-99603 -8909
-99469 -10298
-99241 -12305
-99167 -12888
-99114 -13288
-99085 -13504
-9...

output:

31285949928.7094558477

result:

ok found '31285949928.709457397', expected '31285949928.709457397', error '0.000000000'

Test #11:

score: 0
Accepted
time: 25ms
memory: 14820kb

input:

1000 50
-99999 -569
-99998 -734
-99988 -1610
-99957 -2964
-99943 -3399
-99941 -3461
-99926 -3858
-99887 -4772
-99884 -4834
-99852 -5457
-99821 -5989
-99805 -6257
-99785 -6560
-99729 -7370
-99683 -7968
-99634 -8553
-99612 -8807
-99366 -11251
-99278 -12003
-99223 -12450
-99189 -12717
-98924 -14635
-98...

output:

31331270922.4949191809

result:

ok found '31331270922.494918823', expected '31331270922.494922638', error '0.000000000'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

10 7
-97003 -24299
-89014 -45570
-24303 -97003
-3451 -99941
30342 -95286
99989 1429
77069 63720
23803 97125
-97452 22434
-99819 6019

output:

22074403211.2198350430

result:

ok found '22074403211.219833374', expected '22074403211.219829559', error '0.000000000'

Test #13:

score: 0
Accepted
time: 0ms
memory: 4568kb

input:

99 69
-99999 -511
-99998 -704
-99694 -7827
-97628 -21653
-96532 -26109
-95683 -29068
-95604 -29327
-95333 -30197
-94390 -33026
-93663 -35034
-89230 -45145
-88157 -47207
-84909 -52827
-84336 -53737
-83533 -54976
-79833 -60223
-79323 -60893
-76198 -64761
-75696 -65347
-74794 -66378
-67390 -73883
-5915...

output:

31247417729.6599788070

result:

ok found '31247417729.659976959', expected '31247417729.659965515', error '0.000000000'

Test #14:

score: 0
Accepted
time: 6ms
memory: 6840kb

input:

100 100
-99990 -1440
-99479 -10203
-97709 -21284
-97042 -24144
-94178 -33626
-92144 -38853
-90337 -42888
-88565 -46436
-82545 -56448
-82088 -57112
-79241 -61000
-74743 -66436
-71625 -69785
-70900 -70522
-70015 -71400
-67477 -73804
-64539 -76386
-49557 -86858
-46685 -88434
-30940 -95094
-26367 -96462...

output:

31316997599.7958639860

result:

ok found '31316997599.795864105', expected '31316997599.795856476', error '0.000000000'

Test #15:

score: 0
Accepted
time: 102ms
memory: 45844kb

input:

500 400
-99998 -773
-99972 -2391
-99966 -2640
-99958 -2927
-99955 -3032
-99905 -4379
-99900 -4492
-99700 -7750
-99603 -8911
-99566 -9316
-99507 -9927
-99357 -11326
-99351 -11378
-99153 -12996
-99062 -13670
-98932 -14580
-98836 -15218
-98204 -18872
-97858 -20591
-97700 -21327
-97593 -21813
-97563 -21...

output:

31410954295.3885459900

result:

ok found '31410954295.388545990', expected '31410954295.388881683', error '0.000000000'

Test #16:

score: 0
Accepted
time: 169ms
memory: 85508kb

input:

1000 300
-99998 -766
-99996 -978
-99993 -1243
-99973 -2357
-99969 -2527
-99955 -3029
-99941 -3464
-99929 -3786
-99920 -4018
-99913 -4187
-99880 -4918
-99825 -5929
-99821 -5996
-99793 -6438
-99724 -7431
-99685 -7942
-99664 -8198
-99637 -8524
-99582 -9144
-99369 -11223
-99282 -11969
-99218 -12489
-992...

output:

31412738461.6591799259

result:

ok found '31412738461.659179688', expected '31412738461.659622192', error '0.000000000'

Test #17:

score: 0
Accepted
time: 3ms
memory: 4860kb

input:

1000 5
-99997 -819
-99992 -1341
-99985 -1772
-99978 -2139
-99967 -2599
-99947 -3283
-99942 -3431
-99912 -4207
-99890 -4710
-99875 -5016
-99838 -5707
-99800 -6336
-99765 -6862
-99723 -7448
-99649 -8381
-99621 -8707
-99500 -9997
-99439 -10587
-99296 -11851
-99251 -12223
-99030 -13899
-98892 -14850
-98...

output:

23774219173.3595492020

result:

ok found '23774219173.359550476', expected '23774219173.359542847', error '0.000000000'

Test #18:

score: 0
Accepted
time: 282ms
memory: 85300kb

input:

1000 500
-100000 -365
-99996 -969
-99990 -1476
-99982 -1942
-99973 -2366
-99971 -2448
-99965 -2680
-99952 -3127
-99941 -3459
-99927 -3845
-99897 -4554
-99887 -4768
-99857 -5363
-99816 -6079
-99766 -6852
-99748 -7106
-99705 -7680
-99685 -7941
-99676 -8055
-99638 -8513
-99584 -9120
-99570 -9274
-99499...

output:

31414386060.3031560741

result:

ok found '31414386060.303157806', expected '31414386060.303081512', error '0.000000000'