Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define FASTER() ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
- #define ff first
- #define ss second
- #define pb push_back
- #define all(a) a.begin(), a.end()
- #define dbg(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
- typedef long long ll;
- typedef long double ld;
- using namespace std;
- const ld eps = 1e-7, pi = M_PI;
- struct point {
- ld x, y;
- point() {}
- point(ld x, ld y) : x(x), y(y) {}
- };
- point operator -(point a, point b) {
- return point(a.x - b.x, a.y - b.y);
- }
- ld cross(point a, point b) {
- return a.x * b.y - a.y * b.x;
- }
- ld dot(point a, point b) {
- return a.x * b.x + a.y * b.y;
- }
- ld angle(point a, point b) {
- return abs(atan2(cross(a, b), dot(a, b)));
- }
- ld angle_grad(point a, point b) {
- return abs(atan2(cross(a, b), dot(a, b))) * 180 / pi;
- }
- ld len(point a) {
- return sqrtl(a.x * a.x + a.y * a.y);
- }
- ld get(int n, int m, ld r) {
- ld r_len = len(point(n / 2.0, m / 2.0));
- if(2.0 * r <= (ld) n) { //если окружность целиком внутри прямоугольника
- ld ans = (ld) n * m - pi * r * r;
- return ans;
- }
- if(r_len <= r) { //если прямоугольник целиком внутри окружности
- ld ans = pi * r * r - n * m;
- return ans;
- }
- ld new_y = n / 2.0, new_x = m / 2.0; //центр прямоугольника и окр -- в начале координат => у будет +- у/2
- ld xpos = sqrtl((ld) r * r - new_y * new_y); //ищем координату х на расстоянии new_y от центра окр
- point p1(xpos, new_y), p3(xpos, -1.0 * new_y); //точки в 1 и 4 четвертях плоскости
- ld ang = angle(p1, p3), ang_g = angle_grad(p1, p3); //angle - в радианах, angle_grad - в градусах просто для проверки, не обращай внимание
- ld s_seg = r * r * ang * 0.5; //площадь сектора как r^2 * alpha / 2
- ld sub_sum = abs(xpos) * n + 2 * s_seg; //2 треугольника + 2 сектора
- ld sum = pi * r * r + n * m - 2 * sub_sum;
- return sum;
- }
- void solve() {
- int n, m;
- cin >> n >> m;
- if(n > m) swap(n, m);
- ld l = 0, r = len(point(n / 2.0, m / 2.0));
- while(r - l >= eps) {
- ld m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
- ld fi = get(n, m, m1), se = get(n, m, m2);
- if(fi >= se) {
- l = m1;
- } else {
- r = m2;
- }
- }
- cout << l << endl;
- }
- int main() {
- FASTER();
- cout.precision(30);
- int t;
- cin >> t;
- while(t--) {
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment