zoj2607

扫码查看

题意:zoj2607-LMLPHP如左图,给定A,B,C,D的面积分别为大于等于a,b,c,d,求最小的面积

思路:zoj2607-LMLPHPzoj2607-LMLPHPzoj2607-LMLPHPzoj2607-LMLPHP因为a,b肯定有一个是满的(不然还可压缩到更小),同理,ac,bd,cd都只有一个是满的,所以有可能是对角满的,a,d满的或者,bc满的,如下图zoj2607-LMLPHP

所以,当ad > bc是,ad满,否则bc满(长方形,分成四块,对角面积之积相等)

现在我们来考虑图一:

如题给定,则: p1 * q1 = a;

p2 * q2 = d;

条件: p2 * q1 >= c, p1 * q2 >= b; 即 : p2 / p1 > c / a, p2 / p1 < b / d;

答案为 min(p2 * q1 + p1 * q2) ,代入最上边的等式,得 ans = min(p2 / p1 * a + p1 / p2 * d);

设 t = p2 / p1;

由基本不等式,得 ans >= 2*sqrt(a * b);, 当且仅当 t = sqrt(a * b)取到。。

所以判断 t在不在条件里面,不再就判断端点就行。。

另外一种情况同样考虑即可。。。

只怪比赛时思路太搓了。。数学渣。。。

 #include <iostream>
#include <cstring>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <cstdlib>
#define M0(a) memset(a, 0, sizeof(a))
#define MXN 100010
#define Inf 0xfffff
#define eps 1e-6
double a, b, c, d;
double v;
double p1, p2, q1, q2; void work1(){
p1 = 1.0;
p2 = sqrt(d / a);
if (p2 > d/b) p2 = d /b;
if (p2 < c/a) p2 = c /a;
q1 = a / p1;
q2 = d / p2;
} void work2(){
p1 = 1.0;
p2 = sqrt(c/b);
if (p2 > c/a) p2 = c/a;
if (p2 < d/b) p2 = d/b;
q1 = c / p2;
q2 = b / p1;
} void solve(){
if (a * d >= b * c) work1();
if (a * d < b * c) work2();
v = (p1 + p2) * (q1 + q2);
printf("%.10f\n", v);
printf("%.10f %0.10f %.10f %.10f\n", p1, p2, q1, q2);
} int main(){
// freopen("d.in", "r", stdin);
// freopen("d.out", "w", stdout);
int cas = ;
while (scanf("%lf%lf%lf%lf", &a, &b, &c, &d) != EOF){
solve();
}
fclose(stdin); fclose(stdout);
}
05-11 15:36
查看更多