QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#563130 | #3246. 喵喵花園 | Elegia | AC ✓ | 1441ms | 4152kb | C++23 | 2.1kb | 2024-09-14 03:00:09 | 2024-09-14 03:00:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define db long double
#define eps 1e-9
const int _ = 1003;
struct vec{
db x , y; vec(db _x = 0 , db _y = 0) : x(_x) , y(_y){}
friend vec operator +(vec p , vec q){return vec(p.x + q.x , p.y + q.y);}
friend vec operator -(vec p , vec q){return vec(p.x - q.x , p.y - q.y);}
friend vec operator *(vec p , db q){return vec(p.x * q , p.y * q);}
friend db operator *(vec p , vec q){return p.x * q.x + p.y * q.y;}
friend db operator %(vec p , vec q){return p.x * q.y - p.y * q.x;}
db len(){return sqrt(x * x + y * y);}
}node[_]; int N , K; db len[_];
int main(){
cin >> N >> K; for(int i = 1 ; i <= N ; ++i) cin >> node[i].x >> node[i].y;
node[0] = node[N]; db allen = 0; for(int i = 0 ; i < N ; ++i) allen += (node[i] - node[i + 1]).len();
for(int i = 0 ; i < N ; ++i) len[i] = (node[i + 1] - node[i]).len();
vector < vec > pos; vector < db > lim; vector < int > p;
for(int i = 0 ; i < K ; ++i){
db tar = allen / K * i;
for(int j = 0 ; j < N ; ++j)
if(len[j] < tar) tar -= len[j];
else{pos.push_back(node[j] + (node[j + 1] - node[j]) * (tar / len[j])); p.push_back(j); lim.push_back(len[j] - tar); break;}
}
auto check = [&](db val){
vector < vec > npos;
for(int i = 0 ; i < K ; ++i) npos.push_back(pos[i] + (node[p[i] + 1] - node[p[i]]) * (val / len[p[i]]));
double ans = 0; for(int i = 1 ; i + 1 < npos.size() ; ++i) ans += (npos[i] - npos[0]) % (npos[i + 1] - npos[0]);
return abs(ans) / 2;
};
double ans = 1e18;
while(p.back() != N){
db minlim = 1e9; for(auto t : lim) minlim = min(minlim , t);
db L = 0 , R = minlim;
//for(int j = 0 ; j < 500 ; ++j) ans = min(ans , check(minlim / 500 * j));
for(int i = 1 ; i <= 40 ; ++i){
check(L + (R - L) / 3) > check(R - (R - L) / 3) ? L = L + (R - L) / 3 : R = R - (R - L) / 3;
}
ans = min(ans , min(check(0) , min(check(minlim) , check(L))));
for(int i = 0 ; i < K ; ++i){
lim[i] -= minlim; pos[i] = pos[i] + (node[p[i] + 1] - node[p[i]]) * (minlim / len[p[i]]);
if(lim[i] < eps){++p[i]; lim[i] = len[p[i]];}
}
}
cout << fixed << setprecision(15) << ans; return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1133ms
memory: 3924kb
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.414272308349609
result:
ok found '31414852000.414272308', expected '31414852000.414176941', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1269ms
memory: 3968kb
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.887722015380859
result:
ok found '31415015242.887722015', expected '31415015242.887584686', error '0.000000000'
Test #3:
score: 0
Accepted
time: 1441ms
memory: 4092kb
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.450973510742188
result:
ok found '31414938256.450973511', expected '31414938256.450866699', error '0.000000000'
Test #4:
score: 0
Accepted
time: 632ms
memory: 3936kb
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.421215057373047
result:
ok found '31414085412.421215057', expected '31414085412.421134949', error '0.000000000'
Test #5:
score: 0
Accepted
time: 514ms
memory: 4112kb
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.172359466552734
result:
ok found '31413800407.172359467', expected '31413800407.172279358', error '0.000000000'
Test #6:
score: 0
Accepted
time: 1018ms
memory: 4152kb
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.501049041748047
result:
ok found '31414646664.501049042', expected '31414646664.500938416', error '0.000000000'
Test #7:
score: 0
Accepted
time: 21ms
memory: 3880kb
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.652412414550781
result:
ok found '29387236138.652412415', expected '29387236138.652404785', error '0.000000000'
Test #8:
score: 0
Accepted
time: 35ms
memory: 3824kb
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.949520111083984
result:
ok found '30900099346.949520111', expected '30900099346.949504852', error '0.000000000'
Test #9:
score: 0
Accepted
time: 49ms
memory: 3984kb
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.659145355224609
result:
ok found '31185342172.659145355', expected '31185342172.659126282', error '0.000000000'
Test #10:
score: 0
Accepted
time: 65ms
memory: 3880kb
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.709487915039062
result:
ok found '31285949928.709487915', expected '31285949928.709457397', error '0.000000000'
Test #11:
score: 0
Accepted
time: 78ms
memory: 3940kb
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.494949340820312
result:
ok found '31331270922.494949341', expected '31331270922.494922638', error '0.000000000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3804kb
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.219841003417969
result:
ok found '22074403211.219841003', expected '22074403211.219829559', error '0.000000000'
Test #13:
score: 0
Accepted
time: 11ms
memory: 3808kb
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.659988403320312
result:
ok found '31247417729.659988403', expected '31247417729.659965515', error '0.000000000'
Test #14:
score: 0
Accepted
time: 15ms
memory: 3904kb
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.795894622802734
result:
ok found '31316997599.795894623', expected '31316997599.795856476', error '0.000000000'
Test #15:
score: 0
Accepted
time: 287ms
memory: 4032kb
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.388988494873047
result:
ok found '31410954295.388988495', expected '31410954295.388881683', error '0.000000000'
Test #16:
score: 0
Accepted
time: 439ms
memory: 4088kb
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.659675598144531
result:
ok found '31412738461.659675598', expected '31412738461.659622192', error '0.000000000'
Test #17:
score: 0
Accepted
time: 13ms
memory: 3952kb
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.359550476074219
result:
ok found '23774219173.359550476', expected '23774219173.359542847', error '0.000000000'
Test #18:
score: 0
Accepted
time: 701ms
memory: 3868kb
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.303173065185547
result:
ok found '31414386060.303173065', expected '31414386060.303081512', error '0.000000000'