QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#115239#5904. Twirling Towards Freedomlyx123886a1238860 26280ms4020kbC++142.2kb2023-06-25 11:39:552023-06-25 11:39:56

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-25 11:39:56]
  • 评测
  • 测评结果:0
  • 用时:26280ms
  • 内存:4020kb
  • [2023-06-25 11:39:55]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long//与基准判时,值域最大3e16,不会爆long long
using namespace std;
int read() {
	char ch=getchar();int res=0,fl=1;
	while(ch<'0'||ch>'9'){if(ch=='-') fl=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();}
	return res*fl;
}
const int N=5005;
struct vec{
	int x,y;
}a[N][4],p[4];
vec operator +(vec A,vec B){return (vec){A.x+B.x,A.y+B.y};}
vec operator *(vec A,int k){return (vec){A.x*k,A.y*k};}
vec operator *(int k,vec A){return (vec){A.x*k,A.y*k};}
int operator *(vec A,vec B){return A.x*B.x+A.y*B.y;}
double dis(vec A){return sqrt(1.0*A.x*A.x+1.0*A.y*A.y);}//自乘可能爆long long!!要用double
int n,m,test_case=0;
double calc(vec lim) {
	for(int k=0;k<4;++k) {
		p[k]=a[1][k];//可能不如0,一定要注意!!
		for(int i=2;i<=n;++i) p[k]=((p[k]*lim)<(a[i][k]*lim))?a[i][k]:p[k];
	}
	vec base=p[0]+p[1]+p[2]+p[3],ans=(vec){0,0};
	ans=ans+(((base*lim)>0)?(base*max((m/4)-1,0ll)):(vec){0,0});
	m=m-4*max((m/4)-1,0ll);//把>=8的部分都减4
	vec v[8],maxn;
	v[0]=(vec){0,0};
	maxn=v[0];
	for(int i=1;i<=7;++i) {
		v[i]=v[i-1]+p[(i-1)%4];
		if(m>=i&&(v[i]*(lim))>(maxn*lim)) maxn=v[i];
	} 
//	if(m>=1&&(v0*lim)>(maxn*lim)) maxn=v0;
//	if(m>=2&&(v1*lim)>(maxn*lim)) maxn=v1;
//	if(m>=3&&(v2*lim)>(maxn*lim)) maxn=v2;
//	printf("(%d,%d)(%d,%d)\n",maxn.x,maxn.y,ans.x,ans.y);
	return dis(ans+maxn);
}
void solve() {
	test_case++;
	double Ans=0.0;
	n=read();m=read();
	for(int i=1;i<=n;++i) {
		int x=read(),y=read();
		a[i][0]=(vec){(x-y),(x+y)};
		a[i][1]=(vec){(x+y),-(x-y)};
		a[i][2]=(vec){-(x-y),-(x+y)};
		a[i][3]=(vec){-(x+y),x-y};
	}
//	for(int i=1;i<=n;++i) printf("(%lld,%lld)(%lld,%lld)(%lld,%lld)(%lld,%lld)\n",a[i][0].x,a[i][0].y,a[i][1].x,a[i][1].y,a[i][2].x,a[i][2].y,a[i][3].x,a[i][3].y);
	for(int i=1;i<=100000;++i) {
		int x=(1ll*rand()*rand()-1ll*rand()*rand())%100000,y=(1ll*rand()*rand()-1ll*rand()*rand())%100000;
		Ans=max(Ans,calc((vec){x,y}));
	}
	printf("Case #%lld: %.10lf\n",test_case,Ans);
	return ;
}
signed main()
{
//	freopen("freedom.in","r",stdin);
//	freopen("freedom.out","w",stdout);
	int T=read();
	while(T--) {
		solve();
	}
	return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1172ms
memory: 3740kb

input:

100
4
1
-2 4
1 -2
4 1
0 2
1
4
-5 0
2
5
-1 1
-2 2
10
8
-842 -60
148 -967
327 -600
-546 -346
-196 -267
-833 -156
334 -791
974 -382
-499 -785
519 -657
10
7
444 786
-313 649
-377 954
-872 316
505 714
678 170
40 -971
-290 -649
-824 -797
357 -653
10
9
-384 -28
267 -243
507 -628
-189 -656
373 -879
-115 -81...

output:

Case #1: 6.3245553203
Case #2: 10.0000000000
Case #3: 6.3245553203
Case #4: 8072.6630054772
Case #5: 9582.0846374889
Case #6: 8568.6871806596
Case #7: 3136.8787034248
Case #8: 8904.1807034673
Case #9: 9809.6108995209
Case #10: 6735.7590515101
Case #11: 8863.7475144546
Case #12: 10066.9729313235
Case...

result:

wrong answer read 8568.687180659599 but expected 9520.950057636101 (test case 6)

Subtask #2:

score: 0
Wrong Answer

Test #2:

score: 0
Wrong Answer
time: 26280ms
memory: 4020kb

input:

100
200
59153573
81 -81
-252 252
864 -864
-691 691
-599 599
-520 520
-835 835
334 -334
259 -259
-469 469
374 -374
-36 36
932 -932
-518 518
-882 882
-150 150
-392 392
29 -29
8 -8
-259 259
192 -192
-863 863
-88 88
-219 219
-118 118
485 -485
-953 953
-980 980
-14 14
433 -433
-672 672
352 -352
196 -196
...

output:

Case #1: 82359120550.7561340332
Case #2: 84496965573.2219085693
Case #3: 64984476624.9913101196
Case #4: 109064877368.9813232422
Case #5: 31887460153.9997329712
Case #6: 44597031797.9429397583
Case #7: 14446276745.2589492798
Case #8: 86283226960.1841583252
Case #9: 38768572755.2662582397
Case #10: 2...

result:

wrong answer read 84496965573.221908569336 but expected 84510626188.299926757812 (test case 2)