ohwhatalovelyday

Untitled

Apr 1st, 2022
972
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.71 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define FASTER() ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  4. #define ff first
  5. #define ss second
  6. #define pb push_back
  7. #define all(a) a.begin(), a.end()
  8. #define dbg(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
  9.  
  10. typedef long long ll;
  11. typedef long double ld;
  12.  
  13. using namespace std;
  14.  
  15. const ld eps = 1e-7, pi = M_PI;
  16.  
  17. struct point {
  18.     ld x, y;
  19.     point() {}
  20.     point(ld x, ld y) : x(x), y(y) {}
  21. };
  22.  
  23. point operator -(point a, point b) {
  24.     return point(a.x - b.x, a.y - b.y);
  25. }
  26.  
  27. ld cross(point a, point b) {
  28.     return a.x * b.y - a.y * b.x;
  29. }
  30.  
  31. ld dot(point a, point b) {
  32.     return a.x * b.x + a.y * b.y;
  33. }
  34.  
  35. ld angle(point a, point b) {
  36.     return abs(atan2(cross(a, b), dot(a, b)));
  37. }
  38.  
  39. ld angle_grad(point a, point b) {
  40.     return abs(atan2(cross(a, b), dot(a, b))) * 180 / pi;
  41. }
  42.  
  43. ld len(point a) {
  44.     return sqrtl(a.x * a.x + a.y * a.y);
  45. }
  46.  
  47. ld get(int n, int m, ld r) {
  48.     ld r_len = len(point(n / 2.0, m / 2.0));
  49.    
  50.     if(2.0 * r <= (ld) n) { //если окружность целиком внутри прямоугольника
  51.         ld ans = (ld) n * m - pi * r * r;
  52.         return ans;
  53.     }
  54.    
  55.     if(r_len <= r) { //если прямоугольник целиком внутри окружности
  56.         ld ans = pi * r * r - n * m;
  57.         return ans;
  58.     }
  59.    
  60.     ld new_y = n / 2.0, new_x = m / 2.0; //центр прямоугольника и окр -- в начале координат => у будет +- у/2
  61.     ld xpos = sqrtl((ld) r * r - new_y * new_y); //ищем координату х на расстоянии new_y от центра окр
  62.     point p1(xpos, new_y), p3(xpos, -1.0 * new_y); //точки в 1 и 4 четвертях плоскости
  63.     ld ang = angle(p1, p3), ang_g = angle_grad(p1, p3); //angle - в радианах, angle_grad - в градусах просто для проверки, не обращай внимание
  64.     ld s_seg = r * r * ang * 0.5; //площадь сектора как r^2 * alpha / 2
  65.  
  66.     ld sub_sum = abs(xpos) * n + 2 * s_seg; //2 треугольника + 2 сектора
  67.     ld sum = pi * r * r + n * m - 2 * sub_sum;
  68.     return sum;
  69. }
  70.  
  71. void solve() {
  72.     int n, m;
  73.     cin >> n >> m;
  74.     if(n > m) swap(n, m);
  75.     ld l = 0, r = len(point(n / 2.0, m / 2.0));
  76.     while(r - l >= eps) {
  77.         ld m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
  78.         ld fi = get(n, m, m1), se = get(n, m, m2);
  79.         if(fi >= se) {
  80.             l = m1;
  81.         } else {
  82.             r = m2;
  83.         }
  84.     }
  85.     cout << l << endl;
  86. }
  87.  
  88. int main() {
  89.     FASTER();
  90.     cout.precision(30);
  91.     int t;
  92.     cin >> t;
  93.     while(t--) {
  94.         solve();
  95.     }
  96. }
  97.  
Advertisement
Add Comment
Please, Sign In to add comment