POJ 2722 - Angle and Squares

http://poj.org/problem?id=2722

概要

二次元直交座標系の第一象限にある2点 A, B が与えられる．

半直線 OA, OB によって挟まれている領域に N 個のそれぞれ一辺が l[i] の正方形を並べて，図のように閉じた領域を作る． このとき，その閉じた領域の面積の最大値を答える．

ただし，正方形の各辺は軸に平行でなければならない．

制約

• 0 < N < 10
• 1 <= l[i] <= 20

解法

面積が最大となるのは，すべての正方形の左上の頂点と右下の頂点が，ある直線 y = -x + c 上にあるように並べたときである．

この直線と半直線 OA, OB との交点をそれぞれ C, D とすると，CD の距離は sqrt(2.0) * Σl[i] であることを利用して，二分探索で c の値を求めた．

あとは三角形 OCD から Σ(l[i]*l[i]/2) を引けば面積が求められる．

 1 #include <cstdio>
 2 #include <cmath>
 3 using namespace std;
 4 
 5 inline double sqr(double x) { return x*x; }
 6 
 7 int main()
 8 {
 9   int N;
10   while (scanf("%d", &N) != EOF && N != 0) {
11     double xa, ya, xb, yb;
12     scanf("%lf %lf %lf %lf", &xa, &ya, &xb, &yb);
13     const double a = ya/xa;
14     const double b = yb/xb;
15     double l = 0.0;
16     double s = 0.0;
17     for (int i = 0; i < N; i++) {
18       double x;
19       scanf("%lf", &x);
20       l += x;
21       s += x*x/2.0;
22     }
23 
24     double left = 0.0, right = 1e10;
25     for (int i = 0; i < 100; i++) {
26       const double c = (left+right)/2.0;
27       const double t = fabs(c/(a+1) - c/(b+1));
28       if (t < l) {
29         left = c;
30       } else {
31         right = c;
32       }
33     }
34     const double c = (left+right)/2.0;
35     printf("%.3f\n", c*c*fabs(b-a)/(2.0*(a+1)*(b+1)) - s);
36   }
37   return 0;
38 }