Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <bits/stdc++.h>
- using namespace std;
- float ANS[200];
- int a[200];
- float b[200];
- struct P{int mi; float mx;};
- P info[200];
- float leftover;
- float M;
- bool comparemi(const P&x, const P&y){return x.mi<y.mi;};
- bool comparemx(const P&x, const P&y){return x.mx<y.mx;}
- float solve(int h, float ans, float leftover, float M){
- if(h>=3&&info[1].mi+info[2].mi+info[3].mi<=M){ans=M;}
- else{
- if(info[h].mi<=M/2.000){sort(info+1,info+1+h,comparemx);
- if(h>=2){ans=max(ans,min(M,info[h].mx+info[h-1].mx+leftover));}
- else{ans=max(ans,min(M,info[h].mx+leftover));};
- }
- if(info[h].mi>M/2.000){if(info[h].mi<=M){if(h==1||info[h].mi+info[1].mi>M){ans=max(min(M,info[h].mx+leftover),ans);}
- else{ans=M;}
- }
- else ans=max(solve(h-1,ans,leftover,M),ans);
- };
- };return ans;}
- int main()
- {
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.precision(15);
- int T;
- cin>>T;
- for(int nb=1;nb<T+1;nb++){
- int u,v,N;
- float P;
- float peri=0;
- float leftover=0;
- cin>>N>>P;
- for(int i=1;i<N+1;i++){cin>>u>>v;
- a[i]=min(u,v);b[i]=sqrt(u*u+v*v);peri+=2*u+2*v;
- }
- float M;
- M=(P-peri)/2.000;
- int h=0;
- for(int i=1;i<N+1;i++){if(a[i]<=M*(1-1/sqrt(2)))leftover+=b[i];
- else {h++;info[h].mi=a[i];info[h].mx=b[i];}
- }
- sort(info+1,info+h+1,comparemi);
- float ans=0;
- ANS[nb]=2*solve(h,ans,leftover,M)+peri;}
- for(int nb=1;nb<T+1;nb++)
- cout<<"Case #"<<nb<<": "<<ANS[nb]<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement