# Triangle Partitioning

Mar 19th, 2021
1,077
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2. #define Niloy
3. #define int int64_t
4. #define MAX 1000
5. #define MOD 1e9
6. #define pb push_back
7. #define pairs pair<int, int>
8. #define vi vector<int>
9. #define vb vector<bool>
10. #define vii vector<pairs>
11. #define lb lower_bound
12. #define ub upper_bound
13. #define endl '\n'
14. #define llu unsigned long long
15. using namespace std;
16. /* ----------------------------------------------------------------------------------- */
17.
18. // Input/Output
19. #define fastInput ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
20. #define all(x) x.begin(), x.end()
21.
22. #define scan(a)           scanf("%lld", &a);
23. #define scan2(a, b)       scanf("%lld %lld", &a, &b);
24. #define scan3(a, b, c)    scanf("%lld %lld %lld", &a, &b, &c);
25. #define scan4(a, b, c, d) scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
26.
27. #define scanD(a)          scanf("%lf", &a);
28. #define scanD2(a, b)      scanf("%lf %lf", &a, &b);
29. #define scanD3(a, b, c)   scanf("%lf %lf %lf", &a, &b, &c);
30. #define scanD4(a, b, c, d)scanf("%lf %lf %lf %lf", &a, &b, &c, &d);
31.
32.
33. #define print(a)           printf("%lld\n", a);
34. #define print2(a, b)       printf("%lld %lld\n", a, b);
35. #define print3(a, b, c)    printf("%lld %lld %lld\n", a, b, c);
36. #define print4(a, b, c, d) printf("%lld %lld %lld %lld\n", a, b, c, d);
37.
38. #define printD(a)          printf("%lf\n", a);
39. #define printD2(a, b)      printf("%lf %lf\n", a, b);
40. #define printD3(a, b, c)   printf("%lf %lf %lf\n", a, b, c);
41. #define printD4(a, b, c, d)printf("%lf %lf %lf %lf\n", a, b, c, d);
42. #define printTwoD(a)       printf("%.2lf\n", a);
43.
44. // File I/O
45. #define read(x)  freopen(x, "r", stdin);
46. #define write(x) freopen(x, "w", stdout);
47.
48. // Loops
49. #define rep(i, a, n) for (int i = a; i < n; i++)
50. #define REP(i, a, n) for (int i = a; i <= n; i++)
51. #define rev(i, n, a) for (int i = n - 1; i >= a; i--)
52. #define REV(i, n, a) for (int i = n; i >= a; i--)
53. #define inputArray(a,n) rep(i, 0, n) cin >> a[i];
54. #define copyArray(a,temp,n) rep(i, 0, n) temp[i]=a[i];
55. #define printArray(a,n) rep(i, 0, n) cout << a[i] << " "; cout << endl;
56.
57. /* ----------------------------------------------------------------------------------- */
58.
59. #define Cases  cout << "Case " << ++Case << ": ";
60. #define __test int tt; int Case=0; cin >> tt; while(tt--)
61. #define showTime cerr << "time = " << (clock() / CLOCKS_PER_SEC) << " sec" << '\n';
62.
63. #define dbgA2(A, n, m) {cout<<"--> "<<#A<<" = \n";rep(i, 0, n){rep(j, 0, m){cout<<A[i][j]<<"";}cout<<"\n";}cout<<"\n";}
64. #define dbgA(A, n) {cout<<" --> "<<#A<<" = (";rep(i, 0, n)cout<<A[i]<<" ";cout<<")\n";}
65. #define dbg(args...) {string sss(#args);sss+=',';cout<<" --> ";debugger::call(all(sss), args);cout<<"\n";}
66.
67. /* ----------------------------------------------------------------------------------- */
68.
69. int gcd(int n, int m) { return m ? gcd(m, n % m) : n; }
70. int lcm(int n, int m) { return n / gcd(n, m) * m; }
71.
72. struct debugger {
73.     typedef string::iterator si;
74.     static void call(si it, si ed) {}
75.     template<typename T, typename ... aT>
76.     static void call(si it, si ed, T a, aT... rest) {
77.         string b;
78.         for(; *it!=','; ++it)
79.             if(*it!=' ')
80.                 b+=*it;
81.         cout << b << "=" << a << " ";
82.         call(++it, ed, rest...);
83.     }
84. };
85.
86. /* ----------------------------------------------------------------------------------- */
87. void input() {
88. #ifdef Niloy
89.     read("input.txt");
90.     write("output.txt");
91. #endif
92. }
93.
94. /* ----------------------------------------------------------------------------------- */
95.
96.
97. double findAD(double ab, double ac, double bc, double R) {
98.     double l = 0, r = ab;
99.     rep(i, 0, 100) {
100.         double ad = (l + r) / 2.0;
101.         double x = ad / ab;
102.         double ae = x * ac;
103.         double de = x * bc;
104.
105.         double pABC = (ab + ac + bc) / 2.0;
106.         double pADE = (ad + ae + de) / 2.0;
107.
108.         double ABC = sqrt(pABC * (pABC - ab) * (pABC - ac) * (pABC - bc));
109.         double ADE = sqrt(pADE * (pADE - ad) * (pADE - ae) * (pADE - de));
110.
111.         double areaTra = ABC - ADE;
112.         if (R < (ADE / areaTra)) {
113.             r = ad;
114.         } else {
115.             l = ad;
116.         }
117.     }
118.     return l;
119. }
120.
121. void solve() {
122.     double ab, ac, bc, r;
123.     scanD4(ab, ac, bc, r);
124.     cout << fixed << setprecision(10) << findAD(ab, ac, bc, r) << endl;
125. }
126.
127. int32_t main() {
128.     // input();
129.     // fastInput;
130.     // solve();
131.
132.     __test {
133.         Cases;
134.         solve();
135.     }
136.
137.     // showTime;
138.     return 0;
139. }
140.
RAW Paste Data