QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#282376#3246. 喵喵花園kilo_tobo_tarjen#AC ✓3981ms4100kbC++202.8kb2023-12-11 21:33:342023-12-11 21:33:34

Judging History

This is the latest submission verdict.

  • [2023-12-11 21:33:34]
  • Judged
  • Verdict: AC
  • Time: 3981ms
  • Memory: 4100kb
  • [2023-12-11 21:33:34]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
const char el = '\n';
typedef long long ll;
typedef double ld;
const ld pi = acos(-1);
const ld inf = 1e30, eps = 1e-14;
struct cplx {
  ld x, y;
  ld abs2() const { return x * x + y * y; }
  ld abs() const { return sqrt(abs2()); }
};
cplx operator+(const cplx &a, const cplx &b) { return {a.x + b.x, a.y + b.y}; }
cplx operator-(const cplx &a, const cplx &b) { return {a.x - b.x, a.y - b.y}; }
cplx operator*(const cplx &a, ld b) { return {a.x * b, a.y * b}; }
cplx operator/(const cplx &a, ld b) { return {a.x / b, a.y / b}; }
cplx one(const cplx &a) { return a / a.abs(); }
bool operator<(const cplx &a, const cplx &b) {
  return a.x != b.x ? a.x < b.x : a.y < b.y;
}
bool operator!=(const cplx &a, const cplx &b) { return a < b || b < a; }
bool operator==(const cplx &a, const cplx &b) { return !(a == b); }
ld dot(const cplx &a, const cplx &b) { return a.x * b.x + a.y * b.y; }
ld det(const cplx &a, const cplx &b) { return a.x * b.y - a.y * b.x; }
ld radius(vector<cplx> &a) {
  ld res = (a.back() - a[0]).abs();
  for (int i = 1; i < a.size(); i++) res += (a[i] - a[i - 1]).abs();
  return res;
}
ld area(vector<cplx> &b) {
  // for (auto [x, y] : b) cout << x << ' ' << y << " ; ";
  ld res = 0;
  for (int i = 2; i < b.size(); i++) res += det(b[i - 1] - b[0], b[i] - b[0]);
  // cout << abs(res / 2) << el;
  return abs(res / 2);
}
struct func {
  vector<cplx> a;
  int k;
  ld rad, stp;
  func(vector<cplx> a, int k) : a(a), k(k), rad(radius(a)), stp(rad / k) {}
  ld f(ld x) {
    x -= stp * (ll)(x / stp);
    if (x < 0) x += stp;
    vector<cplx> b;
    cplx c = a[0];
    int p = 0;
    for (int i = 0; i < k; i++) {
      while ((a[p] - c).abs() < x + eps) {
        x -= (a[p] - c).abs();
        c = a[p];
        p = (p + 1) % a.size();
      }
      c = c + one(a[p] - c) * x;
      x = stp;
      b.push_back(c);
    }
    return area(b);
  }
};
random_device r;
default_random_engine e(r());
uniform_real_distribution<> g(0.0, 1.0);
double runtime() { return 1.0 * clock() / CLOCKS_PER_SEC; }
bool intime() { return runtime() < 4; }
ld simu(func &f) {
  ld dx = f.stp;
  ld x = 0, y = f.f(x), res = y;
  int cnt = 0;
  while (dx > 1e-10 && intime()) {
    cnt++;
    ld x2 = x + dx * (g(e) * 2 - 1), y2 = f.f(x2);
    double det = y2 - y;
    res = min(res, y2);
    if (exp(-det / dx) > g(e)) x = x2, y = y2;
    dx *= 0.97;
  }
  for (int i = 1; i <= 100 && intime(); i++) {
    double x2 = x + dx * (g(e) * 2 - 1);
    res = min(res, f.f(x2));
  }
  return res;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << setprecision(15);
  int n, k;
  cin >> n >> k;
  vector<cplx> a(n);
  for (auto &[x, y] : a) cin >> x >> y;
  func f(a, k);
  ld res = inf;
  while (intime()) res = min(res, simu(f));
  cout << res << el;
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3964ms
memory: 3916kb

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.4142

result:

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

Test #2:

score: 0
Accepted
time: 3980ms
memory: 4080kb

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.8877

result:

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

Test #3:

score: 0
Accepted
time: 3981ms
memory: 4100kb

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.4509

result:

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

Test #4:

score: 0
Accepted
time: 3941ms
memory: 3896kb

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.4212

result:

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

Test #5:

score: 0
Accepted
time: 3961ms
memory: 3988kb

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.1723

result:

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

Test #6:

score: 0
Accepted
time: 3974ms
memory: 4020kb

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.501

result:

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

Test #7:

score: 0
Accepted
time: 3945ms
memory: 3996kb

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.6524

result:

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

Test #8:

score: 0
Accepted
time: 3953ms
memory: 4024kb

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.9495

result:

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

Test #9:

score: 0
Accepted
time: 3937ms
memory: 4076kb

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.6591

result:

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

Test #10:

score: 0
Accepted
time: 3933ms
memory: 3888kb

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.7095

result:

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

Test #11:

score: 0
Accepted
time: 3953ms
memory: 4004kb

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.4949

result:

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

Test #12:

score: 0
Accepted
time: 2690ms
memory: 4032kb

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.2198

result:

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

Test #13:

score: 0
Accepted
time: 3728ms
memory: 4100kb

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.66

result:

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

Test #14:

score: 0
Accepted
time: 3769ms
memory: 4020kb

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.7959

result:

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

Test #15:

score: 0
Accepted
time: 3940ms
memory: 4044kb

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.3889

result:

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

Test #16:

score: 0
Accepted
time: 3948ms
memory: 4068kb

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.6597

result:

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

Test #17:

score: 0
Accepted
time: 3925ms
memory: 3932kb

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.3595

result:

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

Test #18:

score: 0
Accepted
time: 3953ms
memory: 4088kb

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.3031

result:

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