QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#115239 | #5904. Twirling Towards Freedom | lyx123886a123886 | 0 | 26280ms | 4020kb | C++14 | 2.2kb | 2023-06-25 11:39:55 | 2023-06-25 11:39:56 |
Judging History
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)