erfanul007

UVa 11648

Apr 15th, 2021
735
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×