H. Degenerate Matrix
time limit per test
memory limit per test
input
output
determinant of a matrix 2 × 2
degenerate
norm ||A|| of a matrix A
You are given a matrix
. Consider any degenerate matrix B such that norm ||A - B|| is minimum possible. Determine ||A - B||.
Input
a and b (|a|, |b| ≤ 109), the elements of the first row of matrix A.
c and d (|c|, |d| ≤ 109) the elements of the second row of matrix A.
Output
||A - B||. Your answer is considered to be correct if its absolute or relative error does not exceed 10 - 9.
Examples
input
1 23 4
output
0.2000000000
input
1 00 1
output
0.5000000000
假设矩阵的四个值为a, b, (第一行两个元素)c, d(第二行两个元素) , 二分枚举最大值mid, 那么a, b, c, d每个数都可以上下浮动mid, 算出a * d的最大值r1, 最小值l1, b * c的最大值r2, 最小值l2, 若[l1, r1]和[l2, r2]相交则可在最大值为mid之内构成一个B矩阵
#include <cstdio>
#include <iostream>
#define maxn 1005
#define MOD 1000000007
typedef long long ll;
using namespace std;
int main(){
ll a, b, c, d;
scanf("%I64d%I64d%I64d%I64d", &a, &b, &c, &d);
double l = 0, r = 2e9, a1, a2, b1, b2, c1, c2, d1, d2;
for(int i = 0; i < 100000; i++){
double mid = (l + r) / 2;
a1 = a + mid, a2 = a - mid;
b1 = b + mid, b2 = b - mid;
c1 = c + mid, c2 = c - mid;
d1 = d + mid, d2 = d - mid;
double t1 = max(max(a1 * d1, a1 * d2), max(a2 * d1, a2 * d2));
double t2 = min(min(a1 * d1, a1 * d2), min(a2 * d1, a2 * d2));
double t3 = max(max(b1 * c1, b1 * c2), max(b2 * c1, b2 * c2));
double t4 = min(min(b1 * c1, b1 * c2), min(b2 * c1, b2 * c2));
if(t4 <= t1 && t2 <= t3)
r = mid;
else
l = mid;
}
printf("%.9lf\n", l);
return 0;
}