QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#83676#3246. 喵喵花園JohnAlfnovAC ✓12ms3828kbC++141.3kb2023-03-03 02:18:242023-03-03 02:18:40

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-03 02:18:40]
  • Judged
  • Verdict: AC
  • Time: 12ms
  • Memory: 3828kb
  • [2023-03-03 02:18:24]
  • Submitted

answer

#include<bits/stdc++.h>
#define double long double
#define sqr(x) ((1ll*(x)*(x)))
#define dist(i,j) (sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j])))
#define A 65
using namespace std;
int x[1005],y[1005];
int n,k;
double jl[1005],dx[1005],dy[1005],md;
double ffabs(double x){
	if(x>0)return x;
	return -x;
}
double calc(double wz){
	int ll=1;
	double he=0;
	for(int i=1;i<=k;++i){
		double zz=wz+(i-1)*md;
		while(he+jl[ll+1]<zz)he+=jl[ll+1],++ll;
		double fl=(zz-he)/jl[ll+1];
		dx[i]=(1-fl)*x[ll]+fl*x[ll+1];
		dy[i]=(1-fl)*y[ll]+fl*y[ll+1];
	}
	dx[0]=dx[k],dy[0]=dy[k];
	dx[k+1]=dx[1],dy[k+1]=dy[1];
	dx[k+2]=dx[2],dy[k+2]=dy[2];
	double ans=0;
	for(int i=1;i<=k;++i){
		ans+=dx[i-1]*dy[i]-dy[i-1]*dx[i];
	}
	return ffabs(ans/2);
}
double solve(double L,double R){
	if(ffabs(R-L)<1e-10)return calc((L+R)/2);
	double zz=(R-L)/A,ans=1e18,wz=L;
	for(double xx=L;xx<=R;xx+=zz){
		double ss=calc(xx);
		if(ans>ss){
			ans=ss;
			wz=xx;
		}
	}
	return min(ans,solve(max(L,wz-4*zz),min(R,wz+4*zz)));
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]);
	x[0]=x[n],y[0]=y[n];
	x[n+1]=x[1],y[n+1]=y[1];
	x[n+2]=x[2],y[n+2]=y[2];
	double zh=0;
	for(int i=1;i<=n+2;++i)jl[i]=dist(i,i-1);
	for(int i=1;i<=n;++i)zh+=jl[i];
	md=zh/k;
	printf("%.12Lf\n",solve(0,md));
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 7ms
memory: 3636kb

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

result:

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

Test #2:

score: 0
Accepted
time: 12ms
memory: 3612kb

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

result:

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

Test #3:

score: 0
Accepted
time: 12ms
memory: 3828kb

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

result:

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

Test #4:

score: 0
Accepted
time: 5ms
memory: 3784kb

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

result:

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

Test #5:

score: 0
Accepted
time: 7ms
memory: 3660kb

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

result:

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

Test #6:

score: 0
Accepted
time: 7ms
memory: 3592kb

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

result:

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

Test #7:

score: 0
Accepted
time: 2ms
memory: 3704kb

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

result:

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

Test #8:

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

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

result:

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

Test #9:

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

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

result:

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

Test #10:

score: 0
Accepted
time: 1ms
memory: 3800kb

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

result:

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

Test #11:

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

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

result:

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

Test #12:

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

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

result:

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

Test #13:

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

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

result:

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

Test #14:

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

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

result:

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

Test #15:

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

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

result:

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

Test #16:

score: 0
Accepted
time: 8ms
memory: 3564kb

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

result:

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

Test #17:

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

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

result:

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

Test #18:

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

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

result:

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