QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#563130#3246. 喵喵花園ElegiaAC ✓1441ms4152kbC++232.1kb2024-09-14 03:00:092024-09-14 03:00:10

Judging History

This is the latest submission verdict.

  • [2024-09-14 03:00:10]
  • Judged
  • Verdict: AC
  • Time: 1441ms
  • Memory: 4152kb
  • [2024-09-14 03:00:09]
  • Submitted

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'