QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#282376 | #3246. 喵喵花園 | kilo_tobo_tarjen# | AC ✓ | 3981ms | 4100kb | C++20 | 2.8kb | 2023-12-11 21:33:34 | 2023-12-11 21:33:34 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'