Advertisement
Guest User

Untitled

a guest
Aug 6th, 2018
334
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.54 KB | None | 0 0
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. float ANS[200];
  5. int a[200];
  6. float b[200];
  7. struct P{int mi; float mx;};
  8. P info[200];
  9. float leftover;
  10. float M;
  11. bool comparemi(const P&x, const P&y){return x.mi<y.mi;};
  12. bool comparemx(const P&x, const P&y){return x.mx<y.mx;}
  13. float solve(int h, float ans, float leftover, float M){
  14. if(h>=3&&info[1].mi+info[2].mi+info[3].mi<=M){ans=M;}
  15. else{
  16. if(info[h].mi<=M/2.000){sort(info+1,info+1+h,comparemx);
  17. if(h>=2){ans=max(ans,min(M,info[h].mx+info[h-1].mx+leftover));}
  18. else{ans=max(ans,min(M,info[h].mx+leftover));};
  19. }
  20. 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);}
  21. else{ans=M;}
  22. }
  23. else ans=max(solve(h-1,ans,leftover,M),ans);
  24. };
  25. };return ans;}
  26. int main()
  27. {
  28. ios::sync_with_stdio(false);
  29. cin.tie(0);
  30. cout.precision(15);
  31. int T;
  32. cin>>T;
  33. for(int nb=1;nb<T+1;nb++){
  34. int u,v,N;
  35. float P;
  36. float peri=0;
  37. float leftover=0;
  38. cin>>N>>P;
  39. for(int i=1;i<N+1;i++){cin>>u>>v;
  40. a[i]=min(u,v);b[i]=sqrt(u*u+v*v);peri+=2*u+2*v;
  41. }
  42. float M;
  43. M=(P-peri)/2.000;
  44. int h=0;
  45. for(int i=1;i<N+1;i++){if(a[i]<=M*(1-1/sqrt(2)))leftover+=b[i];
  46. else {h++;info[h].mi=a[i];info[h].mx=b[i];}
  47. }
  48. sort(info+1,info+h+1,comparemi);
  49. float ans=0;
  50. ANS[nb]=2*solve(h,ans,leftover,M)+peri;}
  51. for(int nb=1;nb<T+1;nb++)
  52. cout<<"Case #"<<nb<<": "<<ANS[nb]<<endl;
  53.  
  54. return 0;
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement