Advertisement
erfanul007

UVa 11648

Apr 15th, 2021
883
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.36 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. // #include <iostream>
  3. // #include <cstdio>
  4. // #include <cstdlib>
  5. // #include <algorithm>
  6. // #include <cmath>
  7. // #include <vector>
  8. // #include <set>
  9. // #include <map>
  10. // #include <queue>
  11. // #include <ctime>
  12. // #include <cassert>
  13. // #include <complex>
  14. // #include <string>
  15. // #include <cstring>
  16. // #include <queue>
  17. // #include <bitset>
  18.  
  19. using namespace std;
  20.  
  21. // #pragma GCC optimize("Ofast,no-stack-protector")
  22. // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  23. // #pragma GCC optimize("unroll-loops")
  24.  
  25.  
  26. #define ll              long long int
  27. #define vi              vector< int >
  28. #define vll             vector< ll >
  29.  
  30. #define sc              scanf
  31. #define pf              printf
  32. #define cspf(i)         pf("Case %d: ", i)
  33. #define spc             pf(" ")
  34. #define line            pf("\n")
  35.  
  36. #define ff              first
  37. #define ss              second
  38. #define mp              make_pair
  39. #define pb              push_back
  40. #define tp(v,j)         get<j>(v)
  41. #define Log(b,x)        (log(x)/log(b))
  42.  
  43. #define FOR(i,x,y)      for(int i = int(x); i < int(y); i++)
  44. #define ROF(i,x,y)      for(int i = int(x)-1; i >= int(y); i--)
  45. #define clr(arr,x)      memset(arr, x, sizeof arr)
  46. #define vout(v,sz)      for(int w=0;w<sz;w++){if(w) spc; cout<<v[w];}
  47. #define all(v)          v.begin(), v.end()
  48. #define rall(v)         v.rbegin(), v.rend()
  49. #define unq(v)          sort(all(v)),(v).resize(unique(all(v))-v.begin())
  50. #define fastIO          ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
  51.  
  52. #define sc1(x)          sc("%d",&x);
  53. #define sc2(x,y)        sc("%d %d", &x, &y)
  54. #define sc3(x,y,z)      sc("%d %d %d", &x, &y, &z)
  55. #define scl1(x)         sc("%lld",&x);
  56. #define scl2(x,y)       sc("%lld %lld", &x, &y)
  57. #define scf1(x)         sc("%lf",&x);
  58. #define scf2(x,y)       sc("%lf %lf", &x, &y)
  59.  
  60. #define pf1(x)          pf("%d",x);
  61. #define pf2(x,y)        pf("%d %d", x, y)
  62. #define pfl1(x)         pf("%lld",x);
  63.  
  64. #define MOD             (int)(1000000007)
  65. #define MaxN            100005
  66. #define inf             0x3f3f3f3f
  67. #define PI              acos(-1.0)  // 3.1415926535897932
  68. #define eps             1e-9
  69.  
  70. template <class T> inline T bigMod(T p,T e,T M){T ret=1; for(;e>0;e>>=1){ if(e&1) ret=(ret*p)%M; p=(p*p)%M;} return (T)ret;}
  71. template <class T> inline T modInverse(T a,T M){return bigMod(a,M-2,M);}
  72. template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
  73. template <class T> inline T lcm(T a,T b) {a=abs(a);b=abs(b); return (a/gcd(a,b))*b;}
  74.  
  75. long double trihi(long double a, long double b, long double c)
  76. {
  77.     long double s = (a+b+c)/2.0;
  78.     return (sqrt(s * (s-a) * (s-b) * (s-c)) * 2.0)/a;
  79.     //return (ar * 2.0)/a; // a bhumi
  80. }
  81.  
  82. long double trapiarea(long double a, long double b, long double hi)
  83. {
  84.     return ((a+b)*hi)/2.0;
  85. }
  86.  
  87. long double percent(long double orgnl, long double cur)
  88. {
  89.     return (cur*100.0)/orgnl;
  90. }
  91.  
  92. long double pertoval(long double orgnl, long double per)
  93. {
  94.     return (orgnl * per)/100.0;
  95. }
  96.  
  97. pair<long double,long double> calcBS(long double a, long double b, long double c, long double d)
  98. {
  99.     long double height = c;
  100.     if(abs(a-b)>eps) height = trihi(abs(a-b), c, d);
  101.     else return {c/2.0, d/2.0};
  102.     //cout<<height<<endl;
  103.     long double lo = 0, hi = height, aelo=0, aehi=c, bflo=0, bfhi=d, ef, eflo=0,efhi = abs(a-b);
  104.  
  105.     while(abs(lo-hi)>eps){
  106.         long double mid = (lo+hi)/2.0;
  107.         long double aemid = (aelo + aehi)/2.0;
  108.         long double bfmid = (bflo + bfhi)/2.0;
  109.         long double efmid = (eflo + efhi)/2.0;
  110.  
  111.         //long double per = percent(height, mid);
  112.  
  113.         ef = a - efmid;
  114.         //cout<<per<<' '<<mid<<' '<<ae<<' '<<bf<<' '<<ef<<'\n';
  115.         long double ar1 = trapiarea(a, ef, mid);
  116.         long double ar2 = trapiarea(ef, b, height-mid);
  117.         if(ar1>ar2){
  118.             hi = mid;
  119.             aehi = aemid;
  120.             bfhi = bfmid;
  121.             efhi = efmid;
  122.         }
  123.         else{
  124.             lo = mid;
  125.             aelo = aemid;
  126.             bflo = bfmid;
  127.             eflo = efmid;
  128.         }
  129.     }
  130.     return {aelo, bflo};
  131. }
  132.  
  133. int main()
  134. {
  135.     #ifndef ONLINE_JUDGE
  136.         clock_t tStart = clock();
  137.         freopen("input.txt", "r", stdin);
  138.         freopen("output.txt", "w", stdout);
  139.     #endif
  140.  
  141.     int t,ca=0; sc1(t);
  142.  
  143.     while(t--){
  144.         long double a,b,c,d;
  145.         cin>>a>>b>>c>>d;
  146.         pair<long double,long double> ans = calcBS(a,b,c,d);
  147.         cout<<"Land #"<<++ca<<": ";
  148.         cout<<fixed<<setprecision(6)<<ans.ff<<' '<<ans.ss<<'\n';
  149.     }
  150.    
  151.  
  152.     #ifndef ONLINE_JUDGE
  153.         fprintf(stderr, "\n>> Runtime: %.10fs\n", (long double) (clock() - tStart) / CLOCKS_PER_SEC);
  154.     #endif
  155.  
  156.     return 0;
  157. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement