Angle and Squares UVA - 1643

Here is a geometric problem. You have an angle and some squares in the first quadrant of the plane rectangular coordinates. The vertex of the angle is fixed on the origin O of the coordinates, and both of its radial lines are specified by the input. The sizes of the squares are also specified by the input, and the squares can shift vertically and horizontally. Now your job is to use the squares and the radial lines of the angle to enclose the maximum area, which excludes the area of the squares (see Figure 1). You should note that the edges of the squares must be parallel to the axes.

Input There are several test cases. Each test case starts with a line consisting of one positive integer N (0 < N < 10), which is the number of the squares. The next line contains four decimal numbers: xa, ya, xb, yb, which denote two points A (xa, ya) and B (xb, yb). The radial lines OA and OB form the angle. Each of the following N lines contains a decimal number, which is the edge length of a square. All the decimal numbers mentioned above are in the range [1, 20]. A test case with N = 0 ends the input, and should not be processed.

Output For each data case, output one line containing a decimal number, which is the maximum area that can be enclosed by the radial lines of the angle and the squares. The value should be rounded to three digits after the decimal point.

Sample Input

1

2.000 3.000 3.000 2.000

1.000

0

Sample Output

2.000

想一想我们就可以知道是当每个正方形对角线相连时最大。

解答过程：

                设有两个未知数x1,x2；  则有x2-x1 = L;   (1)

                我们知道OA，OB斜率  kA，kB，则有x1*kA - x2*kB = L;     (2)

                由（1）和（2）可以得到：

                           x1 = (kB+1)*L/(kA-kB);

                同理可得x2;进而得到  y1,y2;(即C，D两点坐标);

求解面积

x1*y1/2-x2*y2/2+(y1+y2)*(x2-x1)/2-（所有正方形面积）/2

#include <bits/stdc++.h>
using namespace std;
struct point
{
    double x,y;
}A,B,C,D;
int main()
{
    int n;
    while(scanf("%d",&n)&&n)
    {
        double R,area = 0,CD = 0,L = 0,kA,kB;
        scanf("%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y);
        kA = A.y/A.x;
        kB = B.y/B.x;
        if(kB > kA) swap(kA,kB);
        for(int i = 0; i < n;i++)
        {
            scanf("%lf",&R);
            area += R*R/2.0;
            L += R;
        }
        C.x = (kB+1)*L/(kA-kB);
        D.x = (kA+1)*L/(kA-kB);
        C.y = C.x*kA;
        D.y = D.x*kB;
        area = (D.x*C.y-C.x*D.y)/2.0 - area;
        printf("%.3lf\n",area);
    }
    return 0;
}